Re: a^(b^x) mod n?
- From: Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Thu, 23 Jun 2005 10:09:52 +1000
In article <1119476893.618583.126570@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> wrote:
> Jean-Claude Arbaut wrote:
> > 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.
>
> And even if b is unmanageable!!
> Hint: Think "Lagrange's Theorem".
> Further Hint: Think about b^x mod phi(n)
How do you think about b^x mod phi(n) when, as OP says above,
phi(n) is unknown? Presumably n is something like an RSA key,
and computing phi(n) is infeasible.
--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.
- References:
- a^(b^x) mod n?
- From: fredsaf_20055
- Re: a^(b^x) mod n?
- From: Jean-Claude Arbaut
- Re: a^(b^x) mod n?
- From: Pubkeybreaker
- a^(b^x) mod n?
- Prev by Date: Re: IMPORTANT Re: Zero digits in powers
- Next by Date: Re: IMPORTANT Re: Zero digits in powers
- Previous by thread: Re: a^(b^x) mod n?
- Next by thread: Re: a^(b^x) mod n?
- Index(es):
Relevant Pages
|
