Question

Heyaaa

ANSWER FOR 50 POINTS.

It might be a challenger--

Calculate A^-B mod C if B is power of 2?

Answer 1

Using modular multiplication rules:

i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

We can use this to calculate 7^256 mod 13 quickly

7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13

We can substitute our previous result for 7^1 mod 13 into this equation.

7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10

7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13

We can substitute our previous result for 7^2 mod 13 into this equation.

7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9

7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13

We can substitute our previous result for 7^4 mod 13 into this equation.

7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3

We continue in this manner, substituting previous results into our equations.

...after 5 iterations we hit:

7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9

This has given us a method to calculate A^B mod C quickly provided that B is a power of 2.

However, we also need a method for fast modular exponentiation when B is not a power of 2.

hope it help you ｡^‿^｡｡^‿^｡｡^‿^｡｡^‿^｡｡^‿^｡

Answer 2

Answer:

Let's try 5844325mod21:

50515253545556≡25≡4⋅5≡20⋅5≡16⋅5≡17⋅5≡1≡5≡4≡20≡16≡17≡1

So multiplying by 5 six times is the same as multiplying by 1. We want to multiply by 5 a large number of times: 844325. How many times do we multiply by 5 six times? The number of times 6 goes into 844325 is 140720 with a remainder of 5. That remainder is what matters. Multiply by 56 exactly 140720 times and that's the same as multiplying by 1 that many times. Then multiply by 5 just 5 more times, and get 17.

So 5844325≡17mod21.

Step-by-step explanation:

When b is huge, and a and c are coprime, Euler's theorem applies:

ab≡abmodϕ(c)modc

For the example at hand, ϕ(21)=ϕ(3)×ϕ(7)=2×6=12. 844325mod12=5, so 55=5×252≡5×42=80≡17mod21.

When a and c are coprime, but 0<b<ϕ(c), repeated squaring (or using other compositions of powers) is the fastest way to go (manually):

54≡5×53≡5×24≡19194≡(192)2≡582≡(−43)2≡1849≡31314≡(312)2≡(961)2≡522≡2704≡78569≡5×54×((54)4)4≡5×19×78≡5×19×(−23)≡19×(−14)≡−266≡37(mod101)(mod101)(mod101)(mod101)

When a and c are not coprime, let g=gcd(a,c). Let a=g×d and c=g×f, then, assuming b>1:

abmodc=gb×dbmod(g×f)=(g×(gb−1dbmodf))modc

In the example given, gcd(6,14)=2. So 2102×3103mod7, using Euler'r theorem, with ϕ(7)=6, and 102≡0mod6, 2102×3103≡3mod7, so 6103≡(2×3)≡6mod14.