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

Expand Messages
• 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