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

17121Re: [PrimeNumbers] Proving a smooth number +/- 1 prime

Expand Messages
  • Jens Kruse Andersen
    Nov 1, 2005
    • 0 Attachment
      Ed Pegg Jr. wrote:

      > Is the following true?
      > For any number n with less than 20000 digits, if n+1 or n-1 is
      > an easily factorable smooth number, then the primality/non-primality
      > of n can be established with certainty.

      Yes, this and more is true. Any number n can be proven prime/composite
      "easily", in time O(d^2 * log d * log log d) where d = log n, _if_ enough of
      the prime factorization of n+1 or n-1 is known.
      This time is much faster than the average time to find a probable prime.
      The known prime factors of n+/-1 don't have to be small, they just have to be
      proven primes.

      > If so, what is the primality proof method called?

      There are different proof methods with different names, depending on the form
      and factorization percentage of n+/-1. The methods are generally called
      "classical tests".
      See the Prime Pages for details: http://primes.utm.edu/prove/prove3.html

      The popular flexible program PrimeForm/GW implements a BLS proof
      PrimeForm/GW can prove any n up to a million or more digits, if the product of
      known factors of n-1 or n+1 is at least n^(1/3), or a little less for combined
      n-1 and n+1 proofs.

      Some BLS "extensions" not implemented in PrimeForm can prove numbers with less
      n+/-1 factorization.
      David Broadhurst's KP (Konyagin-Pomerance) PARI script can handle n^0.3.
      John Renze's CHG (Coppersmith-Howgrave-Graham) PARI script (currently being
      debugged) can handle down to around n^0.27, depending on the size of n, the
      used computer, and the acceptable time.

      It is utterly hopeless to find enough n+/-1 factorization to easily prove
      primality of a random n above 1000 digits.
      If you get "lucky", you can find a large probable prime cofactor of n-1 or
      n+1. You cannot prove primality of that cofactor significantly easier than of
      n itself, so it doesn't help in practice.

      The largest proven prime n without large n+/-1 factorization is the ECPP
      record with 15071 digits: http://primes.utm.edu/top20/page.php?id=27

      The top-20 for a publicly available program is all with the ECPP program Primo
      with record at 7993 digits: http://www.ellipsa.net/primo/top20.html

      Jens Kruse Andersen
    • Show all 5 messages in this topic