## Re: [PrimeNumbers] the start of AKS-algorithm?

Expand Messages
• ... I do believe that the proposed method is the fastest known (except that you only need to check roots of prime order of course). But I am willing to see
Message 1 of 5 , May 1, 2004
• 0 Attachment
On Sat, 1 May 2004, Décio Luiz Gazzoni Filho wrote:
> On Saturday 01 May 2004 09:46, you wrote:
> > If I wanted to prove that some number N is not equal to the form a^b, then
> > wouldn't I have to start by finding the square root, the third root, the
> > fifth root, and every odd-number root ... and not stop until the result was
> > either integral or less than 2?
>
> Sure, that's a possibility. Not the fastest either, but since you're using
> AKS, you don't care the least about speed after all.

I do believe that the proposed method is the fastest known (except that
you only need to check roots of prime order of course). But I am willing
to see arguments otherwise. See "Detecting perfect powers in essentially
linear time" by Daniel Bernstein at http://cr.yp.to/papers/powers-ams.pdf

>
> > What would be the maximal order of this type of calculation if N is 'm'
> > digits long?
>
> Let's call this largest power k. Then we know that N^(1/k) < 2, and we also
> know that N ~ 10^m. Thus (10^m)^(1/k) < 2, or 10^(m/k) < 2. Now take
> logarithms to base 10 on both sides, you get m/k < 0.3. Thus m < 0.3k, or k >
> m/0.3, or finally, k > 3.3m.
>
> Décio
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.4 (GNU/Linux)
>
> iD8DBQFAk8UoFXvAfvngkOIRApPlAJ9dmZZVwIuhJ1s0wZ0+ww3cUgmvjgCdGRtB
> JTgY0kJULWDT+ZlIcyb0w1E=
> =bk9N
> -----END PGP SIGNATURE-----
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
>
>
• ... Hash: SHA1 ... Asymptotically, perhaps. However, there are faster methods in practice. For instance, to detect whether an integer is a square, one can
Message 2 of 5 , May 1, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 01 May 2004 12:54, you wrote:
> On Sat, 1 May 2004, Décio Luiz Gazzoni Filho wrote:
> > On Saturday 01 May 2004 09:46, you wrote:
> > > If I wanted to prove that some number N is not equal to the form a^b,
> > > then wouldn't I have to start by finding the square root, the third
> > > root, the fifth root, and every odd-number root ... and not stop until
> > > the result was either integral or less than 2?
> >
> > Sure, that's a possibility. Not the fastest either, but since you're
> > using AKS, you don't care the least about speed after all.
>
> I do believe that the proposed method is the fastest known (except that
> you only need to check roots of prime order of course). But I am willing
> to see arguments otherwise. See "Detecting perfect powers in essentially
> linear time" by Daniel Bernstein at http://cr.yp.to/papers/powers-ams.pdf

Asymptotically, perhaps. However, there are faster methods in practice. For
instance, to detect whether an integer is a square, one can check whether the
residue class it lies in, modulo a few primes, is a quadratic residue modulo
that prime. I believe the same can be done for arbitrary powers n, so long as
n | phi(p) for a given prime p, so that there are elements of order n in
Z/pZ.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAlAKPFXvAfvngkOIRAn3oAJ49hes5o3TmUfJ7qhGkKmwPV7H2XgCfRHRs
WJip9rI9hPyDr9+/qgSukqg=
=Xp3u
-----END PGP SIGNATURE-----
• ... Correct as far as it goes, though yuou can optimize by only testing primeth roots because if you ve already tested for a p-th root and the test failed, you
Message 3 of 5 , May 2, 2004
• 0 Attachment
> If I wanted to prove that some number N is not equal to the
> form a^b, then wouldn't I have to start by finding the square
> root, the third root, the fifth root, and every odd-number
> root ... and not stop until the result was either integral or
> less than 2?

Correct as far as it goes, though yuou can optimize by only
testing primeth roots because if you've already tested for
a p-th root and the test failed, you already know that it
isn't a pq-th root.

> What would be the maximal order of this type of calculation
> if N is 'm' digits long?

m *log(10)/log(2).

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.