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

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

Expand Messages
  • Décio Luiz Gazzoni Filho
    May 1, 2004
    • 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-----
    • Show all 5 messages in this topic