10074Re: [PrimeNumbers] Primality proving around 10^14
- Nov 30, 2002mikeoakes2@... wrote:
>Of course there is! If your numbers are less than:
> 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?
then you can do seven strong-SPRP tests to bases 2,3,5,7,11,13,17
to prove primality. See
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
Just a quick example, to prove
we can factor P-1 using very simple trial division to:
The last of these factors can be proven prime using the strong-SPRP
tests as shown above, then we use Theorem 2 on page:
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.
- << Previous post in topic Next post in topic >>