# Large Exponent help

• Jul 24th 2009, 07:18 PM
calccrypto
Large Exponent help
Hi! i need help "exponentiating" large numbers

example:
23207^15416416416464164341748987897644644556446434 643364167389234432442364234531
or, in general:
some number^(some really large number)

and i need the entire value so i can mod it properly.

i know that there are ways of doing it, but i dont understand any of them. can someone tell me how to do it without all sorts of greek letters?

Thanks!

yes, this is about the RSA algorithm...
• Jul 24th 2009, 10:39 PM
CaptainBlack
Quote:

Originally Posted by calccrypto
Hi! i need help "exponentiating" large numbers

example:
23207^15416416416464164341748987897644644556446434 643364167389234432442364234531
or, in general:
some number^(some really large number)

and i need the entire value so i can mod it properly.

i know that there are ways of doing it, but i dont understand any of them. can someone tell me how to do it without all sorts of greek letters?

Thanks!

yes, this is about the RSA algorithm...

You don't need the entire value to mod it properly, what you do is break it down into stages mod-ing as you go along.

CB
• Jul 25th 2009, 01:56 AM
aidan
Quote:

Originally Posted by calccrypto
Hi! i need help "exponentiating" large numbers

example:
23207^15416416416464164341748987897644644556446434 643364167389234432442364234531
or, in general:
some number^(some really large number)

and i need the entire value so i can mod it properly.

i know that there are ways of doing it, but i dont understand any of them. can someone tell me how to do it without all sorts of greek letters?

Thanks!

yes, this is about the RSA algorithm...

If your modulus is less that 10 digits (even if the exponent is hundreds of digits in length) then this can be done using a calculator with 10 digit display.

Lookup the Russian Peasant Algorithm or Exponentiation Algorithm.

$b^e \equiv r \, mod \, m$

as CB stated:
Quote:

You don't need the entire value to mod it properly, what you do is break it down into stages mod-ing as you go along.
CB
for example:

$x^{17} \equiv r \, mod \, m$ = $\left ( \, x^2 (mod \, m) \cdot x^3 (mod \, m) \cdot x^3 (mod \, m) \cdot x^7 (mod \, m) \cdot x^2 (mod \, m) \, \right ) mod \, m$