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




On 22/06/2005 23:48, Pubkeybreaker 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)
>

Ok, I didn't think much about the particular form ;-)

.

Relevant Pages

  • Re: a^(b^x) mod n?
    ... Jean-Claude Arbaut wrote: ... >> 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. ... Hint: Think "Lagrange's Theorem". ...
    (sci.math)
  • Re: a^(b^x) mod n?
    ... > Jean-Claude Arbaut wrote: ... >>> phiis unknown and b^x is so large it can't be used directly. ... and computing phiis infeasible. ... Prev by Date: ...
    (sci.math)
  • RE: how do I test for Integer?
    ... > I wish to test if the results of a calculation is an integer. ... An unknown ... > function perhaps in the stats package? ... Prev by Date: ...
    (microsoft.public.excel.worksheet.functions)
  • Re: .NET features in D2005 Win32
    ... is the neighbor in the next apartment" -- unknown ... Prev by Date: ...
    (borland.public.delphi.non-technical)
  • FS Kings of Steel
    ... garbage playfield, complete, unknown if working or ... not, need room, pickup in Southern New Hampshire ... Prev by Date: ...
    (rec.games.pinball)