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

14818RE: [PrimeNumbers] the start of AKS-algorithm?

Expand Messages
  • Paul Leyland
    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
    • Show all 5 messages in this topic