Line: 1 to 1  

LeetCode5  
Line: 14 to 14  
So we want to be able to compute b^e % m where b is base, e is the exponent, and m is the modulus.  
Changed:  
< <  Modular exponentiation is especially in the field of publickey 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!  
> >  Modular exponentiation is especially useful in the field of publickey 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  
Changed:  
< <  This cannot possibily be computed with directly int's or even long's in C++. We need to use integers, as using doubles will not work because of roundoff error.  
> >  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 roundoff error.  
Changed:  
< <  Fortunately we can use the following modular property:  
> >  Fortunately we can use the following modular property to break a given modular exponentiation into smaller problems.
 
c mod m = (a ⋅ b) mod m c mod m = [(a mod m) ⋅ (b mod m)] mod m  
Changed:  
< <  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.  
> >  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.  
Changed:  
< <  The C++ pow() functions works on doubles, which you should not use. However, the following integer intPow() function can be used instead:  
> >  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:  
Line: 1 to 1  

Added:  
> > 
LeetCode5Due: Oct 26 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 in the field of publickey 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 with directly int's or even long's in C++. We need to use integers, as using doubles will not work because of roundoff error. Fortunately we can use the following modular property: c mod m = (a ⋅ b) mod m c mod m = [(a mod m) ⋅ (b mod m)] mod m 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.
The C++ pow() functions works on doubles, which you should not use. However, the following integer intPow() function can be used instead:
< SyntaxHighlightingPlugin > int intPow(int base, int exp) { int result = 1; while (exp) { if (exp & 1) result *= base; exp /= 2; base *= base; } return result; } < end SyntaxHighlightingPlugin >
Some test cases
Turn in:
Comments
