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

Re: [PrimeNumbers] Nuutti Kuosa et al.'s Factorial Prime search.

Expand Messages
  • Jens Kruse Andersen
    ... If you want old contents of a URL then try the Internet Archive: http://www.archive.org http://web.archive.org/web/20040922151554/http://powersum.dhis.org/
    Message 1 of 5 , Nov 1 11:42 AM
      Phil Carmody wrote:

      > Apparently I have the most complete mirror of Nuutti's site, and
      > the most up-to-date information, but unfortunately some of it is
      > contradictory. Does anyone have any information about completed
      > ranges that is more up-to-date than the info at:
      > http://fatphil.org/Nuutti/
      > http://fatphil.org/Nuutti/minus/minus.html

      If you want old contents of a URL then try the Internet Archive:
      http://www.archive.org

      http://web.archive.org/web/20040922151554/http://powersum.dhis.org/

      --
      Jens Kruse Andersen
    • Jens Kruse Andersen
      ... 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
      Message 2 of 5 , Nov 1 12:31 PM
        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
        (Brillhart-Lehmer-Selfridge).
        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
      Your message has been successfully submitted and would be delivered to recipients shortly.