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

From: "Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx>
Date: 22 Jun 2005 14:48:13 -0700

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)

.

Follow-Ups:
- Re: a^(b^x) mod n?
  - From: Gerry Myerson
- Re: a^(b^x) mod n?
  - From: Jean-Claude Arbaut

References:
- a^(b^x) mod n?
  - From: fredsaf_20055
- Re: a^(b^x) mod n?
  - From: Jean-Claude Arbaut

Prev by Date: Re: Euclidean Geometry in Schools
Next by Date: Re: Real Number Paradox?
Previous by thread: Re: a^(b^x) mod n?
Next by thread: Re: a^(b^x) mod n?
Index(es):
- Date
- Thread

Relevant Pages

Re: a^(b^x) mod n?
... > Jean-Claude Arbaut wrote: ... >>> phiis unknown and b^x is so large it can't be used directly. ... > Further Hint: ... Prev by Date: ...
(sci.math)
Re: XFree86/2 4.5.0 configuration problem
... perhaps you get some hint. ... XFree86 Version 4.5.0 ... informational, not implemented, unknown. ... Missing output drivers. ...
(comp.os.os2.setup.misc)
Re: No positive integers less than on
... > I have been assigned to prove that there are no positive integers less ... My teacher gave the hint to use the well-ordering principle. ... rings of fractions are DENSE. ...
(sci.math)
Re: Series
... Hint for an elementary explicit construction: ... Partition the positive integers into finite sets ...
(sci.math)
Re: questions on positive integers
... there exist positive integers m and n such that 0<- ... Hint: rewrite the inequalities as ...
(sci.math)