An interesting paper: Pomerance-Lucas

[T.Rex]

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

[T.Rex]

The abstract of this paper says:

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

[akruppa]

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 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 M_p in the paper.

My recommendation: don't bother reading it.

Alex

[ewmayer]

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."

[akruppa]

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

[T.Rex]

Originally Posted by T.Rex

Can someone provide me the paper ? (I have no access...)

I've got it, thanks !
T.