mersenneforum.org > Math An interesting paper: Pomerance-Lucas
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-06, 17:10 #1 T.Rex     Feb 2004 France 11101001012 Posts An interesting paper: Pomerance-Lucas 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
2009-01-30, 11:39   #2
T.Rex

Feb 2004
France

3×311 Posts
Testing Mersenne Primes with Elliptic Curves

The abstract of this paper says:
Quote:
 The current primality test in use for Mersenne primes continues to be the Lucas-Lehmer test, invented by Lucas in 1876 and proved by Lehmer in 1935. In this paper, a practical approach to an elliptic curve test of Gross for Mersenne primes, is discussed and analyzed. The most important advantage of the test is that, unlike the Lucas-Lehmer test which requires ${\cal O}(p)$ arithmetic operations and ${\cal O}(p^3)$ bit operations in order to determine whether or not Mp=2p–1 is prime, it only needs ${\cal O}(\lambda)$ arithmetic operations and ${\cal O}(\lambda^3)$ bit operations, with λ≪p. Hence it is more efficient than the Lucas-Lehmer test, but is still as simple, elegant and practical.
Can someone provide me the paper ? (I have no access...)
My email address appears in this paper, as an example.

Thanks !

Tony

Last fiddled with by T.Rex on 2009-01-30 at 11:42

 2009-01-30, 13:20 #3 akruppa     "Nancy" Aug 2002 Alexandria 9A316 Posts I had a quick look. Their idea reduces testing Mp for primality to factoring Mp... In particular, they construct an elliptic curve with a point of order 2[I]p[/I] if Mp is prime and argue that if Mp is composite you might well hit a non-invertible 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 Lucas-Lehmer test and is a good candidate as a replacement to the Lucas-Lehmer test for Mersenne primes." I didn't see any complexity analysis or results of experiments with larger composite Mp in the paper. My recommendation: don't bother reading it. Alex Last fiddled with by akruppa on 2009-01-30 at 19:02 Reason: order 2^p, not p+1..., added "larger composite Mp"
 2009-01-30, 18:32 #4 ewmayer ∂2ω=0     Sep 2002 República de California 5·2,351 Posts Sheesh ... you'd think they'd have at least tried the method out on some much-larger Mersennes, say M31 or even M37. [Rolls eyes] Let me guess: "Extension to larger M(p) such as M31 will require 64-bit integer arithmetic, and will be the subject of a future paper."
 2009-01-30, 19:05 #5 akruppa     "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
2009-01-30, 22:50   #6
T.Rex

Feb 2004
France

93310 Posts
Got it

Quote:
 Originally Posted by T.Rex Can someone provide me the paper ? (I have no access...)
I've got it, thanks !
T.

 Similar Threads Thread Thread Starter Forum Replies Last Post YuL Math 3 2017-06-02 10:51 sean Factoring 2 2006-10-23 21:08 Numbers Math 16 2005-10-16 00:53 Xyzzy Hardware 10 2004-11-23 08:24 devarajkandadai Miscellaneous Math 0 2004-07-27 04:05

All times are UTC. The time now is 01:16.

Fri Feb 3 01:16:37 UTC 2023 up 168 days, 22:45, 1 user, load averages: 0.84, 0.72, 0.83