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

Re: [PrimeNumbers] Best primality testing algorithm...

Expand Messages
  • Chris Caldwell
    ... Specify the size of the integers! IMO: For the first primes the best algorithm is a lookup table. If they are a little larger, trial division (when
    Message 1 of 2 , Apr 6, 2005
    • 0 Attachment
      At 07:25 AM 4/6/2005, Sudarshan Iyengar wrote:

      >Hi,
      >
      >I would be very interested to know the best possible primality testing technique the world ever knew.
      >
      >Best in terms of Checking speed and the magnitude of numbers it can check.
      >
      >I don't think the theoretical result "primes is in P" (AKS algorithm) would be rated the best! (that's what the year 2002 discussion on primenumbers group says).

      Specify the size of the integers!

      IMO: For the first primes the best algorithm is a lookup table. If they are a little larger, trial division (when looking for a single prime, sieves when looking for a list). If you move up to the sizes that show up on the lists of largest known primes ECPP is the winner for general numbers and the classical test can not be beat for specially constructed numbers. But sadly, for incredibly large numbers, the best *proven* method is indeed the only proven polynomial bounded (sans randomness): variations of AKS. These AKS variants are not practical on the size of numbers we can use currently.

      Of course the above assume (semi)sequential computing. Quantum computing will change the world, just not for awhile yet.

      CC


      >-Sudarshan
      >
      >
      >[Non-text portions of this message have been removed]
      >
      >
      >
      >
      >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      >The Prime Pages : http://www.primepages.org/
      >
      >
      >Yahoo! Groups Links
      >
      >
      >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.