mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-01-06, 17:10   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

929 Posts
Default 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
T.Rex is online now   Reply With Quote
Old 2009-01-30, 11:39   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

92910 Posts
Default 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
T.Rex is online now   Reply With Quote
Old 2009-01-30, 13:20   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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"
akruppa is offline   Reply With Quote
Old 2009-01-30, 18:32   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·7·13·43 Posts
Default

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."
ewmayer is offline   Reply With Quote
Old 2009-01-30, 19:05   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-01-30, 22:50   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16418 Posts
Default Got it

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carl Pomerance himself about 210 YuL Math 3 2017-06-02 10:51
Exercise 1.23 in Crandall & Pomerance sean Factoring 2 2006-10-23 21:08
Crandall & Pomerance Numbers Math 16 2005-10-16 00:53
Very interesting K8 paper... Xyzzy Hardware 10 2004-11-23 08:24
Carl Pomerance devarajkandadai Miscellaneous Math 0 2004-07-27 04:05

All times are UTC. The time now is 08:03.


Tue Aug 16 08:03:21 UTC 2022 up 40 days, 2:50, 1 user, load averages: 0.90, 0.95, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔