[math-fun] when is a certifiable prime 'surprisingly easy to prove'?
the elliptic curve method in Mathematica's (NumberTheory`PrimeQ`) package says after 20 seconds that 15085130035827878542455979623747888891433345604817588712723282399687865427853871 is prime. An 80 digit number. Should I expect such timing, or does this large integer have special properties that make it easy to get a certificate? W. quote When \!\(TraditionalForm\`n\) is larger than the value of the option SmallPrime, ProvablePrimeQ uses the Atkin\[Hyphen]Morain test as described above. This primality proving algorithm is suboptimal if the number is within the range of efficient factoring algorithms. When this is the case, a method of V.\[NonBreakingSpace]Pratt is preferable: V.\[NonBreakingSpace]Pratt, \[OpenCurlyDoubleQuote]Every Prime Has a Succinct Certificate,\[CloseCurlyDoubleQuote] SIAM Journal of Computation 4 (1975), pages 214\[Dash]220. An implementation of this algorithm in Mathematica is described in S. Wagon, Mathematica in Action, W. H. Freeman, 1991, Section\[NonBreakingSpace]8.7. end quote
Where angels fear to tread. I gave it to PARI to factor and it instantaneously said that it was prime. R. On Fri, 4 Jun 2004, wouter meeussen wrote:
the elliptic curve method in Mathematica's (NumberTheory`PrimeQ`) package says after 20 seconds that 15085130035827878542455979623747888891433345604817588712723282399687865427853871 is prime. An 80 digit number. Should I expect such timing, or does this large integer have special properties that make it easy to get a certificate?
W.
quote When \!\(TraditionalForm\`n\) is larger than the value of the option SmallPrime, ProvablePrimeQ uses the Atkin\[Hyphen]Morain test as described above. This primality proving algorithm is suboptimal if the number is within the range of efficient factoring algorithms. When this is the case, a method of V.\[NonBreakingSpace]Pratt is preferable: V.\[NonBreakingSpace]Pratt, \[OpenCurlyDoubleQuote]Every Prime Has a Succinct Certificate,\[CloseCurlyDoubleQuote] SIAM Journal of Computation 4 (1975), pages 214\[Dash]220. An implementation of this algorithm in Mathematica is described in S. Wagon, Mathematica in Action, W. H. Freeman, 1991, Section\[NonBreakingSpace]8.7. end quote
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
the elliptic curve method in Mathematica's (NumberTheory`PrimeQ`) package says after 20 seconds that 15085130035827878542455979623747888891433345604817588712723282399687865427853871 is prime. An 80 digit number. Should I expect such timing, or does this large integer have special properties that make it easy to get a certificate?
Yes, that integer has a special property that makes it easy: it's small. The technique is often used on numbers having hundreds of digits, maybe even a thousand.
Where angels fear to tread.
I gave it to PARI to factor and it instantaneously said that it was prime. R.
Angels might indeed fear. I expect that PARI's factor uses factorint when given an integer. That "factors the integer n into a product of pseudoprimes... Use isprime on the result if you want to guarantee primality." But isprime has been found to be buggy, in some versions of PARI. I don't know about the latest version. (See http://groups.google.com/groups?selm=3F037240.6ADC5A06%40nk.ca ) -- Don Reble djr@nk.ca
hi Don and Rich, let me rephrase it: The elliptic curve technique is deterministic, but that doesn't mean all 80 digit prime candidates take equally long. Agreed that a big prime looks rather like -1+2^24036583 or -1+2^20996011. But these are 'relatively easy' because their binary representations are all-1. I was fishing after possibly similar properties. W. ----- Original Message ----- From: "Don Reble" <djr@nk.ca> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Saturday, June 05, 2004 4:56 AM Subject: Re: [math-fun] when is a certifiable prime 'surprisingly easytoprove'?
the elliptic curve method in Mathematica's (NumberTheory`PrimeQ`) package says after 20 seconds that 15085130035827878542455979623747888891433345604817588712723282399687865427853871 is prime. An 80 digit number. Should I expect such timing, or does this large integer have special properties that make it easy to get a certificate?
Yes, that integer has a special property that makes it easy: it's small. The technique is often used on numbers having hundreds of digits, maybe even a thousand.
Where angels fear to tread.
I gave it to PARI to factor and it instantaneously said that it was prime. R.
Angels might indeed fear. I expect that PARI's factor uses factorint when given an integer. That "factors the integer n into a product of pseudoprimes... Use isprime on the result if you want to guarantee primality." But isprime has been found to be buggy, in some versions of PARI. I don't know about the latest version. (See http://groups.google.com/groups?selm=3F037240.6ADC5A06%40nk.ca ) -- Don Reble djr@nk.ca _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Don Reble -
Richard Guy -
wouter meeussen