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

24902Re: Infallible isprime(p) routine for 0<2^32

Expand Messages
  • WarrenS
    Mar 10, 2013
    • 0 Attachment
      If it is your goal to choose X so there are few spsp{2, X},
      then X=735 does pretty well.
      There are 57 spsp{2, 735} below 2^32
      and 1149508 spsp{2, 735} below 2^64.

      The latter is substantially better than Broadhurst's
      X=858945; there are 1311216 spsp{2,858945} below 2^64.
      I make no claim 735 is best, it is merely comparatively good.

      It would probably be possible to devise an infallible isprime test for
      <=64-bit integers by performing spsp(2) and spsp(735) tests, and then hashing
      the 1149508 failures into 8192 bins (each bin representing about 140; need to
      devise the hash function to get good equidistribution)
      and then the content of that table entry tells you which base B to use for a final spsp(B)
      test. (B chosen to kill all fakes in its hash-table bin.)

      This primality test, in net, would involve three spsp tests and one hash-table lookup in a table with 8192 entries; you could probably compute the table in a few days.

      I am in fact working on an infallible 64-bit isprime test, but not using the method I just outlined,instead based on combining an spsp(2) test with a Lehmer test.
      I'll report on that later, if I succeed.
    • Show all 37 messages in this topic