**Due: April 3 at 11:55 pm**

Not really a LeetCode problem, since Leetcode doesn't have this problem.

Instead we use Geeks for Geeks Practice

Your goal is to write a divide and conquer solution for Modular Exponentiation for large numbers

Read about Modular exponentiation here: Modular exponentiation

So we want to be able to compute *b^e % m* where *b* is base, *e* is the exponent, and *m* is the modulus.

Modular exponentiation is especially useful in the field of public-key cryptography. The problem is that for strong cryptography we need *b* to be at least 256 bits long! Moreover, we have to take this large number to an exponent, which can get REALLY big!

Example: (234^432) mod 311 = 140

This cannot possibily be computed directly with (32 bit) int's or even long's in C++. Also - we need to use integers, as using doubles will not work because of round-off error.

Fortunately we can use the following modular property to break a given modular exponentiation into smaller problems.

cmodm= (a⋅b) modmcmodm= [(amodm) ⋅ (bmodm)] modm

You goal is to write a ** divide and conquer algorithm** to do modular exponentiation. The idea is to use the property above to divide the problem into smaller probems that are computible with int's without overflowing. Try to build a solution that minimizes the magnitude of the intermediate results as much as possible.

The C++ **pow()** function in math.c works on doubles, which you should not use. However, the following integer **intPow()** function can be used instead:

intintPow(intbase,intexp) {intresult = 1;while(exp) {if(exp & 1) result *= base; exp /= 2; base *= base; }returnresult; }

base | exponent | modulus | b^e % m |

34523 | 23 | 713 | 391 |

43565 | 335 | 271 | 114 |

43311 | 3661 | 51 | 48 |

544654 | 325 | 5511 | 1639 |

12343 | 32123 | 211 | 83 |

4354 | 211 | 23 | ? |

24411 | 331 | 533 | ? |

43554 | 511 | 411 | ? |

54324 | 35542 | 255 | ? |

34563 | 543255 | 5331 | ? |

- Complete working program code
- Runs for all cases above
- A tight runtime analysis

This topic: Main > WebHome > Math391F2016 > LeetCode5

Topic revision: r7 - 2019-04-01 - JimSkon

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback