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

10074Re: [PrimeNumbers] Primality proving around 10^14

Expand Messages
  • Jack Brennen
    Nov 30, 2002
    • 0 Attachment
      mikeoakes2@... wrote:
      >
      > Having just devoted a GHz-week or so to verifying the primality of about 30
      > million completely-general numbers of about 14 decimal digits using trial
      > division (after ensuring they passed a (relatively) swift
      > pseudo-prime-to-base-x test or two), the question inevitably presents itself:-
      > Is there any quicker way?

      Of course there is! If your numbers are less than:

      341,550,071,728,321

      then you can do seven strong-SPRP tests to bases 2,3,5,7,11,13,17
      to prove primality. See

      http://www.utm.edu/research/primes/prove/prove2_3.html

      If the number is over that threshold, I would suggest factoring
      N+1 or N-1 and using a classical primality proving algorithm. With
      numbers of that range, you can probably factor either N+1 or N-1
      very quickly.

      Just a quick example, to prove

      P=1111111111111123

      we can factor P-1 using very simple trial division to:

      P=2.3.3.3.11.43.43501335491

      The last of these factors can be proven prime using the strong-SPRP
      tests as shown above, then we use Theorem 2 on page:

      http://www.utm.edu/research/primes/prove/prove3_1.html

      to prove P prime.

      But if all you want is a primality prover, use VFYPR or use PARI/GP,
      or I assume Mathematica -- there are no doubt many programs available
      which are quite efficient at proving primes in this range.

      Jack
    • Show all 12 messages in this topic