20041217, 22:37  #12 
Feb 2004
France
3·311 Posts 
Hi,
This thread of discussion is very interesting, and I'm sorry to have been so busy reinstalling my PC at that time. Moloch, I've been at your place some years ago: I was not able to understand why LLT works so well, though I received a good education in Maths before I got my Engineer diploma. But I learnt nothing about Number Theory at that time (26 years ago). The answers you got in this thread talk about "group theory", "finite fields", and many other stuff. This stuff is not useful. I spent several years trying to understand why LLT works. It's clear now. First, many mathematicians now have forgotten the early period when Edouard Lucas (end of XIX) discovered that one can prove a number is prime or not without searching his divisors. At that time, there were no "group theory" and other modern Maths stuff. Edouard Lucas, in fact, was not a "true" Mathematician: He did not provide all the proofs that were needed. If he thought that something was clear/evident, he gave some sort of proof for A ==> B but not for B ==> A, and then he said it's a theorem (A <==> B). Derrick Lehmer then gave complete proofs plus new stuff. If you want to learn how it can be proven, read the chapter 2 of the "Little Book for Greater Primes" of Paulo Ribenboim. You can get it for free at:Springer. But don't believe him totally. He's wrong about the limits of several theorems he gives. They also can be used for numbers like Fermat numbers, not only for Mersenne numbers. If you have a good library near your home, read also the book of Williams: "Edouard Lucas and Primality proving". It's a Great book, but difficult (I understand a very small part of it). But don't read the "Hardy and Wright". It really does not help. According to your math level, understanding the method underneaf the LLT could take months or years ... but it's worth to do it. Reading these books, you can easily see that no "group theory" is needed. The Mathematicians now using "group theory" for proving LLT do not know that they loose a big part of the power of Lucas/Lehmer method. On the web, many of the proofs given for the LLT are so specialized that they can ONLY be used for LLT. So they are of very little use for understanding the nice method discovered by Lucas and improved by Lehmer. Then you could have a look at 2 tries I did for reinventing the wheel about Fermat numbers: First Wheel Second wheel So you can see that LLT method can be used for Fermat numbers. A fact that is not known by many Number Theory experts. Though this looks very difficult, it is very simple for many people. Many people that are giving you explanations in this thread like to talk about things they perfectly know. But they don't like exploring unclear or unproven fields, like the one I proposed in the paper:A primality test for Fermat numbers. Nobody seems to have studied my paper, though Edouard Lucas found quite the same theorem. Or maybe the paper is wrong or very bad. Is it wrong, Mister Silverman ? Though I now understand quite well the theory underneaf the LLT, I still don't understand how it can be computed so quickly, by means of specialized FFT (Fast Fourier Transform). It's too complex for me and I never found a book (several books in fact) explaining all the steps required for understanding the technic used. Some day maybe. People in this forum provided very good explanations of general theory under FFT, but much more is needed. A book would be very useful ! I think some day I'll put on my web site all the documents I've found about Lucas work. But they are all in French, except one. Who is interested ? Have a good day. Tony Carpe Diem 
20041220, 02:33  #13  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
One might find that the proof of part of Lucas's method (by Lehmer's time, more group theory was available) actually corresponds to certain theorems of group theory, except that it's not as general. Quote:
Last fiddled with by cheesehead on 20041220 at 02:41 

20041220, 20:58  #14  
Feb 2004
France
1110100101_{2} Posts 
Quote:
By the way, the Book of HC Williams about E. Lucas has only 4 or 5 pages about the thesis of D. Lehmer. I would be very pleased to be able to read it. Does someone knows where it can be found (on the web) ? Quote:
Quote:
Quote:
Quote:
I learnt group theory at school, long time ago. And I forgot many things. I think I prefer the maths used by Lehmer and Lucas because they enable "amateurs" like me to play with. Quote:
By the way, I've found the official website of Edouard Lucas: Edouard Lucas Site . It contains valuable information about Lucas. And there are a French and an English version ! Regards, Tony 

20041227, 22:20  #15  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
T.Rex,
I was responding to your disparagement of group theory and its use to explain LL. I was defending group theory and its use to explain why LL works. I was discussing why group theory was better than Lucas's work for the purpose of understanding the LL method, not tearing down Lucas's work itself as it seemed you were treating group theory. Quote:
Quote:
Quote:
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2910  20230205 19:37 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 
Exponents to rerelease for firsttime testing: "harmful" errorcodes  GP2  Data  4  20031018 22:08 