Re: a^(b^x) mod n?
- From: "richard miller" <richard@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Wed, 22 Jun 2005 19:00:09 +0100
<fredsaf_20055@xxxxxxxxx> wrote in message
news:1119442304.187215.127240@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> 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.
>
> --
> Fred
>
It can be done efficiently with a computer. You use the fact that
a^(b^x) = ( a^(b^(x-1) ) )^x
And work in reverse, i.e. start with a^b mod n and keep raising to the b'th
power, see further. Denoting
a_1 = a^b mod n,
then
a_2 = a_1^b mod n = a^(b^2)
a_3 = a_2^b mod n = a^(b^3)
and repeat x times to obtain
a_x = a_x-1^b mod n = a^(b^x).
E.g. if x is 1000, then repeat 1000 times.
To raise a^b you use the binary method in the previous respondents reply.
RJM
.
- Follow-Ups:
- Re: a^(b^x) mod n?
- From: fredsaf_20055@xxxxxxxxx
- Re: a^(b^x) mod n?
- From: Ioannis
- Re: a^(b^x) mod n?
- References:
- a^(b^x) mod n?
- From: fredsaf_20055
- a^(b^x) mod n?
- Prev by Date: Re: Orlow cardinality question
- Next by Date: Re: Orlow cardinality question
- Previous by thread: Re: a^(b^x) mod n?
- Next by thread: Re: a^(b^x) mod n?
- Index(es):
Relevant Pages
|
