Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Carl Devore
    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/
      >
      >
      > Yahoo! Groups Links
      >
      >
      >
      >
      >
      >
    • Show all 5 messages in this topic