- #1

- 3

- 1

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter LS1088
- Start date

- #1

- 3

- 1

- #2

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 4,421

- 508

By rather large number do you mean like 10, or like 100000000?

Also is n big as well?

Also is n big as well?

- #3

rcgldr

Homework Helper

- 8,749

- 553

Assuming that "n" is prime or that "a" and "n" are relatively prime, then there is some i where (a^i) mod n = 1. Once you find i, then you're looking for a^(k mod i) mod n.

*update* You can find a^i by using the extended Euclid algorithm, but that doesn't really help.

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Last edited:

- #4

- 1,047

- 779

Yes, we really need to know how big K is. One that works if K is ont too huge is to start finding numbers a^j (mod n) and then multiply the results together to get your final number. For example (assume = means congruence here) using somewhat smaller numbers.

Let's say I wanted 2^20 (mod 111). This is small enough to calculate (it's 70) but let's see how else I can find it:

2^2 = 4 (mod 111 )

Easy enough. But now let's square that result.

2^4 = 4^2 = 16 (mod 111)

Still nothing interesting, but let's square this result this:

2^8 = 16^2 = 256

But that's

256 = 34 (mod 111)

It's much easier now to square 34 than 256. So let's do this a few times.

2^16 = 34^2 = 1156 = 46 (mod 111)

Now by rules of exponents:

2^20 = 2^(16+4)

Which is equal to:

= (2^16)*(2^4)

And since we calculated those, this is:

= (46*16) = 736 = 70 (mod 111)

-Dave K

- #5

rcgldr

Homework Helper

- 8,749

- 553

In addition to repeated squaring, another possible optimization is to find i where a^i mod b = 1, where i will be some integer less than b-1. By using interation it can be determined that 2^36 mod 111 = 1. This means that 2^(j x 36) mod 111 = 1, for any integer value j. This means you only have to determine 2^(k mod 36) mod 111, using repeated squaring.

Rather than using iteration to find i, there is a Euler Totient function, which will produce i or a multiple of i, depending on a and b.

http://en.wikipedia.org/wiki/Euler's_totient_function

Calling the totient function t(), then for b = 111, t(111) = t(3 x 37) = t(3) t(37) = (2) (36) = 72. This eliminates having to iterate to find i, but it may produce a multiple of the smallest possible i. The repeated squaring to produce a product of 2^(k mod 72) mod 111 won't take that many iterations.

The worst case scenario is if b is prime, such as 109. The totient for b if prime is b-1, so t(109) is 108, and you'd have to use repeated squaring to calculate a^(k mod 108) mod 109. (for example, 107 = 1 + 2 + 8 + 32 + 64).

Rather than using iteration to find i, there is a Euler Totient function, which will produce i or a multiple of i, depending on a and b.

http://en.wikipedia.org/wiki/Euler's_totient_function

Calling the totient function t(), then for b = 111, t(111) = t(3 x 37) = t(3) t(37) = (2) (36) = 72. This eliminates having to iterate to find i, but it may produce a multiple of the smallest possible i. The repeated squaring to produce a product of 2^(k mod 72) mod 111 won't take that many iterations.

The worst case scenario is if b is prime, such as 109. The totient for b if prime is b-1, so t(109) is 108, and you'd have to use repeated squaring to calculate a^(k mod 108) mod 109. (for example, 107 = 1 + 2 + 8 + 32 + 64).

Last edited:

Share: