Re: a^(b^x) mod n?




On 22/06/2005 14:11, fredsaf_20055@xxxxxxxxx wrote:

> Given positive integers a,b,x,n is it possible to efficiently compute:
>
> a^(b^x) mod n?
>
> phi(n) is unknown and b^x is so large it can't be used directly.
>
> Or is it known this to be a hard problem?
>
> Thanks.

If b^x is manageable, it's easy by "fast exponentiation".

By manageable, I mean up to 10000 figures, for example.

The trick is writing p=b^x in binary.

Example:

p = 3 = 11(2), then a^p = a^2 * a you

p = 5 = 101(2), then a^p = (a^2)^2*a

Full algo:

r := 1
m := a mod n
while p>0
if p mod 2 = 1 then r := m * r mod n
m := m * m mod n
p := p div 2
wend

Only need roughly O(lg(p)) multiplications.

.

Relevant Pages

  • Re: a^(b^x) mod n?
    ... > Given positive integers a,b,x,n is it possible to efficiently compute: ... > phiis unknown and b^x is so large it can't be used directly. ... then repeat 1000 times. ... To raise a^b you use the binary method in the previous respondents reply. ...
    (sci.math)
  • Re: a^(b^x) mod n?
    ... > Given positive integers a,b,x,n is it possible to efficiently compute: ... > phiis unknown and b^x is so large it can't be used directly. ... You can compute the value b^x and then use the square and multiply ... algorithm. ...
    (sci.crypt)
  • Re: a^(b^x) mod n?
    ... >Given positive integers a,b,x,n is it possible to efficiently compute: ... >phiis unknown and b^x is so large it can't be used directly. ... >Or is it known this to be a hard problem? ... "I can't seem to find any efficient algorithm for this problem"). ...
    (sci.crypt)
  • a^(b^x) mod n?
    ... Given positive integers a,b,x,n is it possible to efficiently compute: ... phiis unknown and b^x is so large it can't be used directly. ... Or is it known this to be a hard problem? ... Prev by Date: ...
    (sci.math)