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

From: Zsuzsanna Doncho (nospam_at_nospam.com)
Date: 06/22/05 

Date: Wed, 22 Jun 2005 15:40:59 +0200

Hi,

fredsaf_20055@yahoo.com 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.
You can compute the value b^x and then use the square and multiply
algorithm. See for example:
http://en.wikipedia.org/wiki/Square-and-multiply_algorithm

Relevant Pages

  • Re: math -- spans of arctans
    ... writing arccot as an alternating finite sum of arccot evaluated ... It follows that a like algorithm exists for arctan. ... positive integers n_i < m. ... Then they are also linearly dependent over Z. ...
    (sci.math)
  • Re: find the largest 1000 values
    ... Secondly, any deterministic algorithm you apply n times on a fixed number of elements is by definition O, since runtime only increases linearly in n. ... I have a large data set of integers, all of them are positive integers from experiment. ... Just iterate over the data, comparing to the smallest of your existing list of the 1000 biggest items, discarding the new element or discarding the smallest old one in each case. ...
    (microsoft.public.vc.language)
  • Re: Evaluation of MegaSnakeOil by "expert"
    ... >> unknown to the public. ... > it's not such a bad algorithm after all. ... bottles of oil claiming to heal cancer, ... job, not that of the outsiders, to prove that what it ...
    (sci.crypt)
  • Re: sshd stopped accepting connections for some hosts???
    ... Yesterday I wrote of problems I was having with MacSSH. ... Selected keyexchange algorithm: diffie-hellman-group1-sha1 ... keyexchange.c:209: Unknown: Raising exception Algorithm negotiation ... Marking fd 10 for closing. ...
    (comp.security.ssh)
  • 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. ... Only need roughly O) multiplications. ...
    (sci.math)
Loading