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

the start of AKS-algorithm?

Expand Messages
  • William Bouris
    Group... 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
    Message 1 of 5 , May 1, 2004
    View Source
    • 0 Attachment
      Group...

      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?

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

      Bill Bouris, Aurora, IL USA


      ---------------------------------
      Do you Yahoo!?
      Win a $20,000 Career Makeover at Yahoo! HotJobs

      [Non-text portions of this message have been removed]
    • Décio Luiz Gazzoni Filho
      ... Hash: SHA1 ... 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. ... Let s
      Message 2 of 5 , May 1, 2004
      View Source
      • 0 Attachment
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        On Saturday 01 May 2004 09:46, you wrote:
        > Group...
        >
        > 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.

        > 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-----
      • Carl Devore
        ... 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 3 of 5 , May 1, 2004
        View Source
        • 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
          >
          >
          >
          >
          >
          >
        • Décio Luiz Gazzoni Filho
          ... Hash: SHA1 ... Asymptotically, perhaps. However, there are faster methods in practice. For instance, to detect whether an integer is a square, one can
          Message 4 of 5 , May 1, 2004
          View Source
          • 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-----
          • Paul Leyland
            ... 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 5 of 5 , May 2, 2004
            View Source
            • 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.