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