Trouble Proving Primes
- To: mathgroup@smc.vnet.net
- Subject: [mg10715] Trouble Proving Primes
- From: Ersek_Ted%PAX1A@mr.nawcad.navy.mil
- Date: Fri, 30 Jan 1998 04:24:51 -0500
Try this:
Open the package for ProvablePrimeQ[n] with the following line.
In[1]:=
<<NumberTheory`PrimeQ`
Now try to use ProvablePrimeQ[n] on any of the following numbers.
25000007273
25000007507
25000009733
25000012901
25000014107
25000015493
25000018973
25000021073
You will get a string of messages that say something like;
Together::modm: Modulus 25000007273 is too large for this
implementation.
Then the program seems to get stuck working on it forever. I let my
computer work on the smallest case above for 14 hours, and never got
an answer.
When it does work ProvablePrimeQ[n] can prove that a Prime on the
order of (10^11) is Prime in a few minutes.
ProvablePrimeQ has several Options (see below). Does anyone know of a
way to specify Options that will give better performance?
Next suppose I want to use ProvablePrimeQ for numbers on the order of
10^20.
Then how do I figure out what Option values are needed?
In[12]:=
Options[ProvablePrimeQ]
Out[12]=
{SmallPrime -> 10000000000, Certificate -> False,
PrimeQMessages -> False,
PollardPTest -> Automatic,
PollardRhoTest -> Automatic,
TrialDivisionLimit -> Automatic}
Thanks,
Ted Ersek