Solve 28633 mod 8633 using: Modular exponentiation
Build an algorithm:
n is our exponent = 8633 y = 1 and u ≡ 2 mod 8633 = 2 See here
n = 8633 is odd
Since 8633 is odd, calculate (y)(u) mod p (y)(u) mod p = (1)(2) mod 8633 (y)(u) mod p = 2 mod 8633 2 mod 8633 = 2 Reset y to this value
Determine u2 mod p
u2 mod p = 22 mod 8633 u2 mod p = 4 mod 8633 4 mod 8633 = 4 Reset u to this value
Cut n in half and take the integer
8633 ÷ 2 = 4316
n = 4316 is even
Since 4316 is even, we keep y = 2
Determine u2 mod p
u2 mod p = 42 mod 8633 u2 mod p = 16 mod 8633 16 mod 8633 = 16 Reset u to this value
Cut n in half and take the integer
4316 ÷ 2 = 2158
n = 2158 is even
Since 2158 is even, we keep y = 2
Determine u2 mod p
u2 mod p = 162 mod 8633 u2 mod p = 256 mod 8633 256 mod 8633 = 256 Reset u to this value
Cut n in half and take the integer
2158 ÷ 2 = 1079
n = 1079 is odd
Since 1079 is odd, calculate (y)(u) mod p (y)(u) mod p = (2)(256) mod 8633 (y)(u) mod p = 512 mod 8633 512 mod 8633 = 512 Reset y to this value
Determine u2 mod p
u2 mod p = 2562 mod 8633 u2 mod p = 65536 mod 8633 65536 mod 8633 = 5105 Reset u to this value
Cut n in half and take the integer
1079 ÷ 2 = 539
n = 539 is odd
Since 539 is odd, calculate (y)(u) mod p (y)(u) mod p = (512)(5105) mod 8633 (y)(u) mod p = 2613760 mod 8633 2613760 mod 8633 = 6594 Reset y to this value
Determine u2 mod p
u2 mod p = 51052 mod 8633 u2 mod p = 26061025 mod 8633 26061025 mod 8633 = 6631 Reset u to this value
Cut n in half and take the integer
539 ÷ 2 = 269
n = 269 is odd
Since 269 is odd, calculate (y)(u) mod p (y)(u) mod p = (6594)(6631) mod 8633 (y)(u) mod p = 43724814 mod 8633 43724814 mod 8633 = 7302 Reset y to this value
Determine u2 mod p
u2 mod p = 66312 mod 8633 u2 mod p = 43970161 mod 8633 43970161 mod 8633 = 2292 Reset u to this value
Cut n in half and take the integer
269 ÷ 2 = 134
n = 134 is even
Since 134 is even, we keep y = 7302
Determine u2 mod p
u2 mod p = 22922 mod 8633 u2 mod p = 5253264 mod 8633 5253264 mod 8633 = 4400 Reset u to this value
Cut n in half and take the integer
134 ÷ 2 = 67
n = 67 is odd
Since 67 is odd, calculate (y)(u) mod p (y)(u) mod p = (7302)(4400) mod 8633 (y)(u) mod p = 32128800 mod 8633 32128800 mod 8633 = 5407 Reset y to this value
Determine u2 mod p
u2 mod p = 44002 mod 8633 u2 mod p = 19360000 mod 8633 19360000 mod 8633 = 4814 Reset u to this value
Cut n in half and take the integer
67 ÷ 2 = 33
n = 33 is odd
Since 33 is odd, calculate (y)(u) mod p (y)(u) mod p = (5407)(4814) mod 8633 (y)(u) mod p = 26029298 mod 8633 26029298 mod 8633 = 803 Reset y to this value
Determine u2 mod p
u2 mod p = 48142 mod 8633 u2 mod p = 23174596 mod 8633 23174596 mod 8633 = 3624 Reset u to this value
Cut n in half and take the integer
33 ÷ 2 = 16
n = 16 is even
Since 16 is even, we keep y = 803
Determine u2 mod p
u2 mod p = 36242 mod 8633 u2 mod p = 13133376 mod 8633 13133376 mod 8633 = 2583 Reset u to this value
Cut n in half and take the integer
16 ÷ 2 = 8
n = 8 is even
Since 8 is even, we keep y = 803
Determine u2 mod p
u2 mod p = 25832 mod 8633 u2 mod p = 6671889 mod 8633 6671889 mod 8633 = 7213 Reset u to this value
Cut n in half and take the integer
8 ÷ 2 = 4
n = 4 is even
Since 4 is even, we keep y = 803
Determine u2 mod p
u2 mod p = 72132 mod 8633 u2 mod p = 52027369 mod 8633 52027369 mod 8633 = 4911 Reset u to this value
Cut n in half and take the integer
4 ÷ 2 = 2
n = 2 is even
Since 2 is even, we keep y = 803
Determine u2 mod p
u2 mod p = 49112 mod 8633 u2 mod p = 24117921 mod 8633 24117921 mod 8633 = 5952 Reset u to this value
Cut n in half and take the integer
2 ÷ 2 = 1
n = 1 is odd
Since 1 is odd, calculate (y)(u) mod p (y)(u) mod p = (803)(5952) mod 8633 (y)(u) mod p = 4779456 mod 8633 4779456 mod 8633 = 5407 Reset y to this value
Determine u2 mod p
u2 mod p = 59522 mod 8633 u2 mod p = 35426304 mod 8633 35426304 mod 8633 = 5105 Reset u to this value
Cut n in half and take the integer
1 ÷ 2 = 0
Because n = 0, we stop
We have our answer
Final Answer
28633 mod 8633 ≡ 5407
What is the Answer?
28633 mod 8633 ≡ 5407
How does the Modular Exponentiation and Successive Squaring Calculator work?
Free Modular Exponentiation and Successive Squaring Calculator - Solves xn mod p using the following methods:
* Modular Exponentiation
* Successive Squaring This calculator has 1 input.
What 1 formula is used for the Modular Exponentiation and Successive Squaring Calculator?
Successive Squaring I = number of digits in binary form of n. Run this many loops of a2 mod p
