Difference: LeetCode5 (1 vs. 7)

Revision 72019-04-01 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode5

Changed:
<
<
Due: April 1 at 11:55 pm
>
>
Due: April 3 at 11:55 pm
  Moodle Link

Revision 62019-03-24 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode5

Changed:
<
<
Due: Oct 26 at 11:55 pm
>
>
Due: April 1 at 11:55 pm
 
Changed:
<
<
Moodle Link
>
>
Moodle Link
  Not really a LeetCode problem, since Leetcode doesn't have this problem.

Revision 52016-11-14 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode5

Line: 73 to 73
 

Comments


<--/commentPlugin-->
\ No newline at end of file
Added:
>
>
Solutions

Revision 42016-10-25 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode5

Line: 23 to 23
 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.

Deleted:
<
<

 
c mod m = (ab) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m

Line: 55 to 54
 
34523 23 713 391
43565 335 271 114
43311 3661 51 48
Changed:
<
<
544654 325 5511 913
>
>
544654 325 5511 1639
 
12343 32123 211 83
4354 211 23 ?
24411 331 533 ?

Revision 32016-10-20 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode5

Due: Oct 26 at 11:55 pm

Added:
>
>
Moodle Link
 Not really a LeetCode problem, since Leetcode doesn't have this problem.

Instead we use Geeks for Geeks Practice

Revision 22016-10-19 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

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 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!
>
>
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
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 round-off 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 round-off 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 = (ab) 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:
  %CODE{"c++"}% int intPow(int base, int exp)

Revision 12016-10-19 - JimSkon

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="Math391F2016"

LeetCode5

Due: 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 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 with directly int's or even long's in C++. We need to use integers, as using doubles will not work because of round-off error.

Fortunately we can use the following modular property:

c mod m = (ab) 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

base exponent modulus b^e % m
34523 23 713 391
43565 335 271 114
43311 3661 51 48
544654 325 5511 913
12343 32123 211 83
4354 211 23 ?
24411 331 533 ?
43554 511 411 ?
54324 35542 255 ?
34563 543255 5331 ?

Turn in:

  1. Complete working program code
  2. Runs for all cases above
  3. A tight runtime analysis

-- Jim Skon - 2016-10-19

Comments


<--/commentPlugin-->
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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