Lesson An Example of Successive Squaring

Algebra ->  Divisibility and Prime Numbers -> Lesson An Example of Successive Squaring      Log On


   

This Lesson (An Example of Successive Squaring) was created by by math_tutor2020(3817) About Me : View Source, Show
About math_tutor2020: Middle school, high school, and college math tutor
This lesson will go over an example number theory problem dealing with the Successive Squaring Method.
This is useful when needing to compute large exponential expressions in some modulus.

Example: Compute 3^107 (mod 131)

The first task is to break the exponent 107 down into smaller chunks such that each piece is a power of 2.
Why powers of 2? You'll see in a moment, but you can probably guess it has something to do with the repeated squaring operations.

Subtract off the largest power of 2 from 107, then subtract the largest power of 2 from that result, and so on.
Keep this process going until you hit 0.
This is what your scratch work could look like
107 - 64 = 43
43 - 32 = 11
11 - 8 = 3
3 - 2 = 1
1 - 1 = 0

Circle the middle column of values (64, 32, etc).
Add them up to see that 64 + 32 + 8 + 2 + 1 = 107

This must mean 3^107 = 3^( 64 + 32 + 8 + 2 + 1 ) = 3^64*3^32*3^8*3^2*3^1

--------------------------------------------------------------------------

Summary so far
3^107 = 3^64*3^32*3^8*3^2*3^1 (mod 131)

What next? We'll start with the base 3 and successively square it (hence the name of this technique) while also reducing it mod 131 to avoid the result getting too large.
3^1 = 3 (mod 131)
3^2 = 9 (mod 131)
3^4 = (3^2)^2 = (9)^2 = 81 (mod 131)
3^8 = (3^4)^2 = (81)^2 = 6561 = 11 (mod 131)
3^16 = (3^8)^2 = (11)^2 = 121 (mod 131)
3^32 = (3^16)^2 = (121)^2 = 14641 = 100 (mod 131)
3^64 = (3^32)^2 = (100)^2 = 10000 = 44 (mod 131)

Here is the tidied up list
3^1 = 3 (mod 131)
3^2 = 9 (mod 131)
3^4 = 81 (mod 131)
3^8 = 11 (mod 131)
3^16 = 121 (mod 131)
3^32 = 100 (mod 131)
3^64 = 44 (mod 131)
Spreadsheet software can make quick work of this, but it could be helpful to know how to do this by hand.

Let's toss out the rows we don't need.
We'll end up with this:
3^1 = 3 (mod 131)
3^2 = 9 (mod 131)
3^8 = 11 (mod 131)
3^32 = 100 (mod 131)
3^64 = 44 (mod 131)

We're almost done.

3^107 = 3^64*3^32*3^8*3^2*3^1 (mod 131)
3^107 = 44*100*11*9*3 (mod 131) ........... plug in items from list above
3^107 = 4400*11*9*3 (mod 131)
3^107 = 77*11*9*3 (mod 131)
3^107 = 847*9*3 (mod 131)
3^107 = 61*9*3 (mod 131)
3^107 = 549*3 (mod 131)
3^107 = 25*3 (mod 131)
3^107 = 75 (mod 131)

Verified by WolframAlpha
https://www.wolframalpha.com/input?i=3%5E107+%3D+75+%28mod+131%29

There is likely a faster more efficient calculation pathway, but I decided to show the full step-by-step breakdown.

Note: In the jump from step 3 to step 4 we reduced 4400 to 77 since 4400 = 77 (mod 131). Both give the same remainder when dividing over 131
This process of multiplying the first pair of numbers, then reducing (if necessary) is the basic algorithm I followed to compute the last block shown above.
This lesson has been accessed 951 times.