20090106, 17:10  #1 
Feb 2004
France
949_{10} Posts 
An interesting paper: PomeranceLucas
A Paper by Carl Pomerance.
Hi, Mr Pomerance has produced an interesting paper where he talks about the important contribution of Edouard Lucas to the primality tests. He provides an equivalence between the LLT and a very different kind of test. He read the thesis about E. Lucas and the wonderful book of HC Williams on the work of E. Lucas. To be read, I think. Regards, Tony 
20090130, 11:39  #2  
Feb 2004
France
949_{10} Posts 
Testing Mersenne Primes with Elliptic Curves
The abstract of this paper says:
Quote:
My email address appears in this paper, as an example. Thanks ! Tony Last fiddled with by T.Rex on 20090130 at 11:42 

20090130, 13:20  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I had a quick look. Their idea reduces testing M_{p} for primality to factoring M_{p}...
In particular, they construct an elliptic curve with a point of order 2^{[I]p[/I]} if M_{p} is prime and argue that if M_{p} is composite you might well hit a noninvertible coordinate before finishing p iterations (that's the λ≪p bit). That's plain wrong. They show that it saves time for p=23, and write "Our complexity analysis and computing experiments show that the elliptic curve test is more efficient than the LucasLehmer test and is a good candidate as a replacement to the LucasLehmer test for Mersenne primes." I didn't see any complexity analysis or results of experiments with larger composite M_{p} in the paper. My recommendation: don't bother reading it. Alex Last fiddled with by akruppa on 20090130 at 19:02 Reason: order 2^p, not p+1..., added "larger composite Mp" 
20090130, 18:32  #4 
∂^{2}ω=0
Sep 2002
República de Califo
2^{2}·2,939 Posts 
Sheesh ... you'd think they'd have at least tried the method out on some muchlarger Mersennes, say M31 or even M37. [Rolls eyes]
Let me guess: "Extension to larger M(p) such as M31 will require 64bit integer arithmetic, and will be the subject of a future paper." 
20090130, 19:05  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Well ok, they did try on M31, but since that's a genuine Mersenne prime, both methods as expected need the full number of iterations. But that's the only two exponents they list, in particular no larger composite Mp. So, point well taken...
Alex 
20090130, 22:50  #6 
Feb 2004
France
13·73 Posts 
Got it

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Carl Pomerance himself about 210  YuL  Math  3  20170602 10:51 
Exercise 1.23 in Crandall & Pomerance  sean  Factoring  2  20061023 21:08 
Crandall & Pomerance  Numbers  Math  16  20051016 00:53 
Very interesting K8 paper...  Xyzzy  Hardware  10  20041123 08:24 
Carl Pomerance  devarajkandadai  Miscellaneous Math  0  20040727 04:05 