What are the Primality Tests ( not factoring! ) for Fermat Numbers?
 

Hi

I have been dealing with factors of fermat numbers F12,F13,F14

I know that primality status of some fermat numbers F33,F34... are still unknown. Many are working on factoring but not a long way has been travelled on primality check.

As far as i know, best primality test is Pepin's Test (1877) which is quite old in my opinion. Of course Proth's theorem is like a generalization of Pepin's test with unrestricting the base.

Here is my question, is there any more efficient new algorithms to test primality of fermat numbers, or can you think any sort of improvements on this subject.
Currently, Pepin's Test deals with the whole fermat number in modular arithmetic(2^2^N). May be someone can show up with more iterations but dealing with just the exponent of fermat number (which is 2^N)

???

Aren't Fermat numbers F5 and above, all composite ?

[QUOTE=dsouza123]Aren't Fermat numbers F5 and above, all composite ?[/QUOTE]

Probably, but that has not been proven. All Fermat numbers up to F32 have been shown to be composite (besides obviously F0-4), and other larger Fermat numbers have been shown to be composite by finding factors. As for Erasmus's question, Pepin's test is the best I heard of, and said to be the best on the Prime Pages.

3^[(Fn-1)/2] = (-1) mod Fn
Is this Pepin's test?

[QUOTE=Cyclamen Persicum]3^[(Fn-1)/2] = (-1) mod Fn
Is this Pepin's test?[/QUOTE]

Kinda Rabin-Miller test on base 3 =))) But here it is deterministic and explicit...

[QUOTE=Erasmus]Here is my question, is there any more efficient new algorithms to test primality of fermat numbers, or can you think any sort of improvements on this subject.
Currently, Pepin's Test deals with the whole fermat number in modular arithmetic(2^2^N). May be someone can show up with more iterations but dealing with just the exponent of fermat number (which is 2^N)

???[/QUOTE]

Pepin's test may be old, but its asymptotic complexity is the same as for a Mersenne of similar size, i.e. both are examples of numbers of special form (and which are not composite by construction, i.e. they do need to be tested) which permit as fast a deterministic primality test as is known.

And like Mersenne-mod, Fermat-mod multiply permits a fast DWT-based algorithm.

Re. a way of proving the number while dealing only with quantities the size of the exponent - that's what trial factoring does. But if that fails to turn up a small factor, the only way we know of to establish the character of such numbers is to resort to methods that use full-blown multiplies modulo the number being tested.

Why not using Lucas-Lehmer test ?
 

I think Lucas-Lehmer test also works for Fermat numbers.
Why not using it, starting with 5 ?

Examples:
F2=2^2^2+1=2^4+1=17
u0=5
u1=5^2-2=6 mod 17
u2=6^2-2=0 mod 17

F3=2^2^3+1=2^8+1=257
u0=5
u1=5^2-2=23
u2=23^2-2=+/-13 mod 257
u3=13^2-2=+/-90 mod 257
u4=90^2-2=+/-126 mod 257
u5=126^2-2=+/-60 mod 257
u6=60^2-2=0 mod 257

Interesting - it also gives 0 for F4, but not for F5.

There might be something there (though it would require more than just numerical evidence to validate or disprove the algorithm), but even if we could do an LL-style style test on the Fermats, it would be no faster than the Pe'pin test.

Interesting, I checked up through F13 and the test worked every time. (Although the interesting thing isn't that it fails for most Fermat numbers, it's that it works only on F1, F2, F3, and F4.) I thought Lucas sequences were useful when you knew all the factors of N+1, whereas for Fermat factors, you know all the factors of N-1. Does anyone know enough about this to be able to figure out if the test is rigorous?

Tony, did you figure this out by numerical experimentation? Very nice!

Proof Of Infinitude Of Prime Fermat Numbers
 

I think that there are infinitely many Fermat primes, even Fermat primes are rare and there is a slim or no chance of finding another Fermat prime. Can you draw a complicated shape, instead of a triangle, pentagon, 17-gon, 257-gon and 65537-gon to discover a Fermat prime?

I mean, go search for very large Fermat primes, 2^(2^n)+1 for n greater than 32, other than the first five Fermat primes.

There's already such a search going on.

[url]http://www.prothsearch.net/fermat.html#Summary[/url]

[QUOTE=philmoore]Interesting, I checked up through F13 and the test worked every time. (Although the interesting thing isn't that it fails for most Fermat numbers, it's that it works only on F1, F2, F3, and F4.) I thought Lucas sequences were useful when you knew all the factors of N+1, whereas for Fermat factors, you know all the factors of N-1. Does anyone know enough about this to be able to figure out if the test is rigorous?

Tony, did you figure this out by numerical experimentation? Very nice![/QUOTE]
Not exactly numerical experimentation.
I studied the S(n)=S(n-1)^2-2 function and I discovered some nice symmetries and relationships for Mersenne numbers. Since I saw the same
properties for Fermat numbers, I'm convinced (but no proof) that my formula:
u(0) = 5
u(N)=u(N-1)^2-2
Fn is prime <==> u(2^n-2) = 0 (mod Fn)
is correct for Fermat numbers.
I plan since years to spend time to describe what I found in order to ask people if it is some representation of well-known properties of (so complex)
Lucas numbers, or not.
I don't know if using FFT for testing the primality of Fermat numbers is faster than Pepin's test. But since there exist multi-threaded Mersenne test programs, it may help. Even the modulo Fn can be easily written.
Who could help about the Maths behind this ?
Tony

Unfortunately, the smallest Fermat Number with unknown primality status (F33) has over 2.58 billion digits...

In Williams P+1 factoring, whether your starting element s has order p+1 or p-1 depends on whether s^2-4 isn't or is a qudaratic residue (mod p). I believe the same is happening here.

For Mersenne numbers with odd exponent > 1 and s=4, 4^2-4=12=4*3 is a QNR, because 4 is trivially a QR and 3 is a QNR by quadratic reciprocity [2^(2*e+1)-1 == 1 (mod 3) which is a QR, and both are 3 (mod 4)], so 4*3 is a QNR (mod 2^(2*e+1)-1) and we'll properly conduct a p+1 primality test.

For Fermat numbers F_m, m>0, with s=5, s^2-4 = 21 = 3*7, 3 is a QNR (mod F_m) [as 2^(2^m)+1 == 2 (mod 3) is a QNR and F_m is not 3 (mod 4)], 7 is a QNR [as (2^(2^m)+1 == 3 or 5 (mod 7), both 3 and 5 are QNR (mod 7)], so 3*7 is a QR (mod F_m) and we get a p-1 primality test just like Pepin's test in (Z/ZF_m)*.

Alex

[QUOTE=T.Rex]I don't know if using FFT for testing the primality of Fermat numbers is faster than Pepin's test. But since there exist multi-threaded Mersenne test programs, it may help. Even the modulo Fn can be easily written.
Who could help about the Maths behind this ?
Tony[/QUOTE]

I think you're confusing the mathematical algorithms for verifying primality (LL and Pe'pin) with the algorithms (FFT and DWT) for efficiently effecting the large-integer modular multiplies that dominate the computational cost for these primality tests once the numbers being tested get big. FFT is simply a way (probably the fastest way known on modern microprocessors) to speedily effect large-integer multiplies, which can be shown to be nothing more than cyclic convolutions of the vectors of digits that the large input integers are broken into on the computer hardware (e.g. if you were doing a Fermat-mod multiply using a wordsize of 16 bits, that amounts to representing the input integer in base-2^16 form). The various flavors of the DWT all have the aim of further speeding the modmul by building the modular reduction directly into the fast transform used to effect the multiply. So one can use an FFT-based multiply for any kind of input number, whether or not a DWT exists (or better, has been found) for the number we are using as the modulus. Here are the key differences between Fermat and Mersenne-number moduli:

* Fermat are of form 2^n + 1, so require an acyclic (sometimes called "negacyclic") convolution if we are doing an implicit mod (i.e. a DWT). Unmodified FFT-based mul gives a cyclic convolution, but there is a well-known way to multiply the inputs by certain roots of unity (the DWT weights for acyclic convolution) so as to get an acyclic convolution as output. For Fermats it is most natural to use a power-of-2 wordsize (which yields a power-of-2 FFT length), but if a non-power-of-2 transform length is desired, one can layer a second set of DWT weights - the same type as used in the Crandall/Fagin Mersenne-mod DWT - on top of the acyclic-effecting ones to achieve this.

* Mersenne are of form 2^n - 1, so require a cyclic convolution if we are doing an implicit mod, thus no modification of the FFT is needed here. However, for Mersennes the exponent n is prime, so we can't break the input numbers into fixed-wordsize chunks. The C/F DWT allows us to break the inputs into variable word sizes (think of timekeeping, which breaks the day into a variable-base-representation: base-24 for hours and base-60 for minutes and seconds) in a systematic way so that the "folding" which occurs naturally in a (cyclic or negacyclic) convolution happens at the desired spot, i.e. at the (n)th bit of the underlying multiword integer without n needing to be a power of two or even to be composite.

For more details on this, here is a reference:

[url]http://www.mersenneforum.org/attachments/pdfs/F24.pdf[/url]

Anyway, nice bit of work re. the LL-style test for Fermats - even if it gives no practical advantage over Pe'pin, a new mathematical method for testing primality of this class of numbers is always interesting to have, since it may yield new insights.

Maybe too complex for me ???
 

Hi EwMayer,
I need time for understanding all your explanations. I think I'm starting to understand the differences between the 2 computations.
About the proof, I think I have a proof (based on Ribenboim's book) about: [Fn Prime] ==> [Fn divides S(Fn-2)] , with: S0=5 , Sn=S(n-1)^2-2
I'm working on the reverse.

You seem to say it is a new Math result ? I would be very pleased if it's true. :smile: :w00t: But I guess it is an old forgotten result.
Are there some more Mathematicians around that could help us about this ?
Tony

"Edouard Lucas and Primality Testing"
 

Hi,
Does someone has this book and can see if Mr Williams H. C. talks about using LLT for Fermat numbers ?
By the way, if you have read it, do you think it is a must-have book ? It seems very expensive.
Thanks.
Tony

Yes, I have the book and will check this for you soon. (I'm in the middle of finals, so it may not be until next week.) It is a fascinating book if you find history of mathematics interesting. The book covers the entire history of primality testing, but focuses mainly on Lucas and Lehmer. Lucas is credited with the most significant insight in the history of primality testing, namely, that it is possible to prove a number prime without testing all possible factors. There is also an extensive discussion of pre-computer mechanical sieving devices. Three years ago, I attended the Lehmer conference in Berkeley, and several of Lehmer's sieves, including his bicycle chain sieve, were on display at the conference. Although the math is mostly available also in other sources, I did find Hugh Williams explanation of Lucas sequences quite clear. It is expensive, and I wonder if it can be obtained cheaper through sources other than the publisher. I remember that Powell's (in Portland Oregon) had copies a year or two ago for $80.

Williams' book about Lucas and Lehmer test
 

Hi Philmoore,
Thanks for your help! Yes, I think I will buy the book. I've visited the bookshops and the University library and they have very few things about Number Theory. (They may think people interested with such old Maths are crazy ...)
Tony

Proof of LLT for Fermat numbers
 

I have 95 % of a proof for my primality test for Fermat numbers based on the Lucas-Lehmer test, but I still don't know if it is or not kind of forgotten (because not useful) already known old maths.
Tony

[QUOTE=T.Rex]I have 95 % of a proof for my primality test for Fermat numbers based on the Lucas-Lehmer test, but I still don't know if it is or not kind of forgotten (because not useful) already known old maths.
Tony[/QUOTE]

Congratulations, Tony! Anyway, a proof can only be 100% or 0% correct... :smile: (just kidding)

You deserve admiration because, in case the proof was known, you rediscovered it on your own. :showoff:

Luigi

99 % now.
 

Yes, you're right. It is 0 or 100 % !
In fact, I wanted to say that I had still to find solutions for proving the remaining parts. And sometimes, the 5% left may take very long ! or never succeed.
Now, I only have some details to prove, I think. Or maybe I'll find THE problem and failed to have a complete proof!
What is surprising me is that all books I've read (not so much) and all web-sites about Primality proving I've looked at say that this kind of test in only for N-1 numbers, like Mersenne numbers, not for N+1 numbers.
Even if I fail or if it is already known, it helped me to understand all the not explained and horrible details of the LLT that appear in the excellent Ribenboim's book. Also I found some small mistakes, I think.
Tony

Some kind of success
 

Hi,
I've succeeded in proving the following: :smile:
[quote]Fn = 2^2^n +1
T[0]=40
T[i]=2*T[i-1]*(T[i-1]+1)
Fn is prime iff T[2^n-2] = 0 (mod Fn)
[/quote]
Example:
[quote]n=3
F[3] = 2^2^3+1 = 2^8+1 = 257

T[0] = 40
T[1] = 196
T[2] = 124
T[3] = 160
T[4] = 120
T[5] = 256
T[6] = T[2^4-2] = 0


n = 4
F[4] = 2^2^4+1 = 2^16+1 = 65537

T[ 0] = 40
T[ 1] = 3280
T[ 2] = 27224
T[ 3] = 30934
T[ 4] = 9569
T[ 5] = 40282
T[ 6] = 32909
T[ 7] = 6993
T[ 8] = 36880
T[ 9] = 32764
T[10] = 32800
T[12] = 34816
T[11] = 32640
T[13] = 65536
T[14] = T(2^4-2) = 0
[/quote]
But I did not succeed in proving the LLT for Fermat numbers: :redface:
[quote]Fn = 2^2^n +1
S[0]=4
S[i]=T[i-1]^2-2
Fn is prime iff S[2^n-2] = 0 (mod Fn)
[/quote]
though experiments have shown that it works up to F13.
Any suggestion ?

Hi, Tony! I just found a reference that seems to apply to your algorithm. The article is "Biquadratic Reciprocity and a Lucasian Primality Test" by Pedro Berrizbeitia and T. G. Berry in Mathematics of Computation, latest issue, 73(2004), pages 1559-1564. You can retrieve the article at:
[url]http://www.ams.org/journals/mcom/2004-73-247/[/url]
I haven't yet read it carefully, but it claims to prove that Lucas tests can be used to prove primality for certain numbers of the form h*2^n +/- 1. For 2^n+1 (h=1), the seed (starting point for the Lucas test) is -5/6 mod 2^n+1, which is equivalent to 3(2^(2^n)-1)/5 for the Fermat number 2^(2^n)+1. Not the same seed you used, but it does at least apparently establish that you can use a Lucas test to prove the primality of a Fermat number!

Lucas and Lehmer were so extraordinary !
 

Hi Phil,
Thanks for the reference!
Since I'm just an "amateur", I have no way to access the AMS documents and the subscription for an individual is too high for me. Nevertheless, I was able to find a preprint of the document and I will read it asap.
About Williams' book, I've bought it thru Amazon and I have started to read it. It's a marvellous book, providing many and many useful and clear information. Very valuable! Nevertheless, I think the chapter about Lehmer's work is a little short.
I was working on a proof for: S(0)=5, S(i)=S(i-1)^2-2, Fn=2^2^n+1 is prime iif Fn | S(i-2) when I received the book. I had found a way by using P=sqrt(R) and, though many details were missing, I think I was able to build a proof. Then I found in Williams' book that he did the same (use sqrt(R) instead of an integer) in his Ph D Thesis, but not exactly. So, I was both proud to be able to find it after him and also so sad not to be the first ! The theorems described in Williams' book are not exactly the same as the one I'm working on. So maybe there is some place for me. I'll let you know about my search later. (my wife is saying it's time to lunch!)
Tony

Lucas Sequences can be used for N+1 or N-1 numbers
 

I forgot to say:
I don't understand why Mr Ribenboim says in his famous book "Little book for Bigger Primes" that Lucas Sequences are good only for N-1 numbers like Mersenne numbers. Williams' book clearly shows that Lucas Sequences can be used for both N-1 and N+1 numbers, like Fermat numbers. I think Ribenboim wanted to limit the theory to his needs: prove the LLT for Mersenne numbers; but he should clearly say that he's only showing the simpler part of Lucas Sequences theory.
Also, I'd like to say that I think Lucas Sequences and LLT and other primality proofs are only tools for showing a fundamental property of primes: symmetry.
Tony

I've built the proof for "Testing Fermat numbers by means of LLT"
 

Hi,
In post #7 of this thread: "Why not using Lucas-Lehmer test ?" I proposed to use the LLT (starting with S_0=5) for proving the primality of Fermat numbers. After some search, I was not able to build a proof.
Now, with the help of Mr Williams'book : "Edouard Lucas and primality testing", I thing I have a correct proof. :smile: I "just" need to write a LaTeX document with a mathematical proof. That should take several weeks ... :sad:

If someone knows that a proof already exists ... I'd like to be warned. :question:

In the same thread post #14, Alex (akruppa) said it is evident that my proposal leads to a test like the Pepin's test. I'm missing the theory underneath. Which book should I read in order to understand Alex' explanations ?

Thanks,
Regards,
Tony

Hi,

The draft of the proof is available at: [URL=http://tony.reix.free.fr/Mersenne/]http://tony.reix.free.fr/Mersenne/[/URL] : "A LLT-like test for proving the primality of Fermat numbers, based on Lucas Sequences. Proof (.pdf)."

Let me know if you think the proof is correct.

Finally the proof takes only 3 pages, thanks to Lehmer's theorems.

The document is 8 pages long since I provide the Lehmer's theorems plus some proofs and some numerical data .

Tony

A new proof by Zhi-Hong Sun
 

Hi,

I've found the following vrey interesting paper:
[url]http://202.195.112.2/xsjl/szh/prime3F.pdf[/url]
which provides a new proof for the LLT and a new proof for my primality test for Fermat numbers (seed=5), described in the previous posts. Look at top of page 6.
The paper deals with primality test for numbers of the form k2^n+/-1 .

Mister Sun says that he gives a "new primality test for Fermat numbers". That's not true, since I provided my proof before. But maybe someone else proved it before me ! The most important is to make progress and to have more skilled people coming and studying the LLT !

Regards,

Tony

[QUOTE=T.Rex;106065]Mister Sun says that he gives a "new primality test for Fermat numbers". That's not true, since I provided my proof before. But maybe someone else proved it before me ! The most important is to make progress and to have more skilled people coming and studying the LLT ![/QUOTE]

But all other things being equal, establishing priority is important - did you alert him to your work, Tony? Does his paper add anything significnantly new beyond what you proved?

Nice finding... (a) of the paper, (b) of the 3 year old thread...
Of course the authors of the paper did several additional things,
and some might say your paper was not really published, and there are so many documents on the web that one cannot check if their content is to be taken seriously, etc. etc... but if they or the referee were readers of this forum, they could have mentioned your results, if not as reference, at least as a comment at the end of the paper...

[QUOTE=ewmayer;106072]But all other things being equal, establishing priority is important - did you alert him to your work, Tony?[/QUOTE]I sent him an email but then I received an error message. I'll try again.
Since Sun added Remark 3.2 about K. Inkeri who proved the same kind of LLT for Fermats but with a seed of 8, first I think Zhi-Hong did not saw my work, and second if he had knew he would have added a remark, I think.
There are 2 guys in me: one wants the Mersenne/LLT theory to be deeper studied; so Zhi-Hong is welcome ! The other part of me would like to be famous (at least for my children and for the memory of my wife); so I would have be pleased to see a word about me in Sun's paper. But it is mainly my fault: I should have published it in [url]http://arxiv.org/[/url] . I'll do (when I have time ...).
[QUOTE]Does his paper add anything significantly new beyond what you proved?[/QUOTE]Compared to what I proved: no. The result is exactly the same. The proof is different. Main result is Theorem 3.1 page 5 and he can prove the LLT for Mersennes and the LLT for Fermats. And this is VERY IMPORTANT ! Because many Number Theory books and people divide the primality tests into two categories: the N-1 tests (including the LLT for Mersennes) and the N+1 tests (including the Pépin test for Fermats). My opinion is that LLT can be used for any kind of number and that LLT and Pépin test are equivalent (I proved this for Fermat numbers). But, up to now, I never found a proof that a N-1 number can be proved prime by Pépin's test ... (Reminder: N-1 and N+1 means that N is completely or partially factorized).

About Sun's theorem 3.1 , I cannot say how difficult is the finding of the appropriate (b,c) used by is Theorem. If someone could help ...

Now, we have 3 proofs of this theorem, [URL="http://tony.reix.free.fr/Mersenne/PrimalityTest2FermatNumbers.pdf"]mine[/URL], [URL="robert.gerbicz.googlepages.com/Fermatnumbers.pdf"]Gerbicz[/URL], and now [URL="http://202.195.112.2/xsjl/szh/prime3F.pdf"]Sun[/URL]. Good !

Tony

I need an endorsement for arXiv
 

Hi,

I plan to submit my paper (proof of LLT for Fermat, with seed 5) to arXiv.org .
Due to their new rules, and since I never submitted to arXiv, I need an "endorsement from another user to submit a paper to category math.NT (Number Theory)." Paper is available here: [url]http://tony.reix.free.fr/Mersenne/PRIMALITYTEST2FERMATNUMBERSarXiv.pdf[/url]

I've already asked 3 people (I do not know them, but they worked around Mersenne or LLT or Primality proving) who have authority to endorse me, but no answer yet ...

So, if someone in this forum has (or knows someone who has) the authority to endorse me for publishing my paper in arXiv, that would greatly help me !

I've understood the "endorsement guy" does not have to check all the paper. He only has to check that it follows good Maths and LaTeX rules.

Information provided by arXiv.org is available below.
If you agree to endorse me, please follow their instructions:

"(Tony Reix should forward this e-mail to someone who's registered as an endorser for the math.NT (Number Theory) subject class of arXiv.)
Tony Reix requests your endorsement to submit an article to the math.NT section of arXiv. To tell us that you would (or would not) like to endorse this person, please visit the following URL: [url]http://arxiv.org/auth/endorse.php?x=RD7EN8[/url]
If that URL does not work for you, please visit [url]http://arxiv.org/auth/endorse.php[/url] and enter the following six-digit alphanumeric string: Endorsement Code: RD7EN8 "

Thanks,

Regards,

Tony



Endorsement needed for math.NT

You must get an endorsement from another user to submit a paper to category math.NT (Number Theory).

ArXiv is an openly accessible, moderated repository for scholarly papers in specific scientific disciplines. Material submitted to arXiv is expected to be of interest, relevance, and value to those disciplines. Endorsement is necessary but not sufficient to have a paper accepted in arXiv; arXiv reserves the right to reject or reclassify any submission.

We've sent an email message to [email]tony.reix@XXXXXXXX[/email] with a unique endorsement code; please forward this e-mail to someone authorized to endorse you for category math.NT (Number Theory.)

Who is qualified to endorse?

To endorse another user to submit to the math.NT (Number Theory) subject class, an arXiv submitter must have submitted 4 papers to any of math.AC, math.AG, math.AP, math.AT, math.CA, math.CO, math.CT, math.CV, math.DG, math.DS, math.FA, math.GN, math.GR, math.GT, math.HO, math.KT, math.LO, math.MG, math.MP, math.NA, math.NT, math.OA, math.OC, math.PR, math.QA, math.RA, math.RT, math.SG, math.SP or math.ST earlier than three months ago and less than five years ago.

You can find out if a particular person is qualified to endorse by looking up one or more of his papers and clicking on the link "Which of the authors of this paper can endorse?" at the bottom of the abstract.

It would be good for you to find an endorser who is connected with you: for instance, if you're a graduate student, your thesis advisor or another professor in your department would be a good choice. Otherwise, you should choose an endorser whose work is related to the subject of your paper.

[QUOTE=T.Rex;106417]Hi,

I plan to submit my paper (proof of LLT for Fermat, with seed 5) to arXiv.org .
Due to their new rules, and since I never submitted to arXiv, I need an "endorsement from another user to submit a paper to category math.NT (Number Theory)." Paper is available here: [url]http://tony.reix.free.fr/Mersenne/PRIMALITYTEST2FERMATNUMBERSarXiv.pdf[/url]

I've already asked 3 people (I do not know them, but they worked around Mersenne or LLT or Primality proving) who have authority to endorse me, but no answer yet ...

So, if someone in this forum has (or knows someone who has) the authority to endorse me for publishing my paper in arXiv, that would greatly help me !

I've understood the "endorsement guy" does not have to check all the paper. He only has to check that it follows good Maths and LaTeX rules.

Information provided by arXiv.org is available below.
If you agree to endorse me, please follow their instructions:

"(Tony Reix should forward this e-mail to someone who's registered as an endorser for the math.NT (Number Theory) subject class of arXiv.)
Tony Reix requests your endorsement to submit an article to the math.NT section of arXiv. To tell us that you would (or would not) like to endorse this person, please visit the following URL: [url]http://arxiv.org/auth/endorse.php?x=RD7EN8[/url]
If that URL does not work for you, please visit [url]http://arxiv.org/auth/endorse.php[/url] and enter the following six-digit alphanumeric string: Endorsement Code: RD7EN8 "

Thanks,

Regards,

Tony



Endorsement needed for math.NT

You must get an endorsement from another user to submit a paper to category math.NT (Number Theory).

ArXiv is an openly accessible, moderated repository for scholarly papers in specific scientific disciplines. Material submitted to arXiv is expected to be of interest, relevance, and value to those disciplines. Endorsement is necessary but not sufficient to have a paper accepted in arXiv; arXiv reserves the right to reject or reclassify any submission.

We've sent an email message to [email]tony.reix@XXXXXXXX[/email] with a unique endorsement code; please forward this e-mail to someone authorized to endorse you for category math.NT (Number Theory.)

Who is qualified to endorse?

To endorse another user to submit to the math.NT (Number Theory) subject class, an arXiv submitter must have submitted 4 papers to any of math.AC, math.AG, math.AP, math.AT, math.CA, math.CO, math.CT, math.CV, math.DG, math.DS, math.FA, math.GN, math.GR, math.GT, math.HO, math.KT, math.LO, math.MG, math.MP, math.NA, math.NT, math.OA, math.OC, math.PR, math.QA, math.RA, math.RT, math.SG, math.SP or math.ST earlier than three months ago and less than five years ago.

You can find out if a particular person is qualified to endorse by looking up one or more of his papers and clicking on the link "Which of the authors of this paper can endorse?" at the bottom of the abstract.

It would be good for you to find an endorser who is connected with you: for instance, if you're a graduate student, your thesis advisor or another professor in your department would be a good choice. Otherwise, you should choose an endorser whose work is related to the subject of your paper.[/QUOTE]


May I suggest to all of you who are working on these ideas (e.g. new
prime tests for Mersenne/Fermat numbers) that you read the dissertation
of Jon Grantham (a former student of Carl Pomerance)?????

All of these tests (including the purported new ones) are essentially "the
same".

You are looking to test a (purported) prime P where either P-1 or P+1
is a power of two. All of these tests are just variations of a more general
test that works in GP(P^2). They are just disguised ways of doing
exponentiations either in Z/PZ* (the multiplicative sub-group of GF(P^2)
whose order is P-1), or in the twisted sub-group. (order P+1). Note
that the order of the field GF(P^2) = P^2 - 1 = (P+1)(P-1) so it should
not come as a surprise that there is a 'LL type' test for Fermat numbers.

You should also read the paper of Eric Bach & J. Shallit in which they
extend the P-1 factoring algorithm to *any* cyclotomic polynomial in P
(which of course can be used as a generator in GF(p^k) for chosen k)

ALL of these efforts should be couched in the general language of the
various subgroups of GF(P^k). Indeed, the Lucas-Lehmer type tests
can be extended to primes *other* than those for which P-1 = 2^k
of P+1 = 2^k. They can be extended to primes for which ANY cyclotomic
polynomial in P = 2^k simply by going to higher order finite fields.

I would suggest that if you really want to publish this kind of work, that
you should totally re-phrase your efforts using (as Grantham did) the
Frobenius endomorphisms of the (sub-groups of) the higher degree
finite fields. Otherwise, all you are doing is picking out "special cases
in disguised form".

[QUOTE=R.D. Silverman;106443]May I suggest to all of you who are working on these ideas (e.g. new
prime tests for Mersenne/Fermat numbers) that you read the dissertation
of Jon Grantham (a former student of Carl Pomerance)?????

<sniip>


[/QUOTE]

May I also point out that a LL type test for Fermat numbers is NOT going to
be any faster than Pepin's test? For F_n = 2^2^n + 1, both are going to
take 2^n modular multiplications/squarings mod F_n.

Hi Sir,
[QUOTE=R.D. Silverman;106443]May I suggest to all of you who ...[/QUOTE]Thanks for the suggestion ! I just want to learn. But, since my level of Maths is only "basic", I need time, examples, explanations, ...

Are you talking of this [URL="http://www.pseudoprime.com/pseudo.html"]Grantham[/URL] ?
About the paper of Eric Bach & J. Shallit, do you have a title or a link ?
[QUOTE]All of these tests are just variations of a more general test that works in GP(P^2). They are just disguised ways of doing exponentiations [/QUOTE]I DO agree with you. However, do you know about some paper or book that clearly explains this, saying that Pépin or LLT (seed=5 or 6) are equivalent for proving the primality of Fermat numbers, or giving the number (3 or other) to be used for a Pépin's test for Mersennes ?
If not, you should write such a paper.
Open the Ribenboim or the Crandall/Pomerance books: they say that Pépins is for N+1 numbers and LLT for N-1 numbers.

[QUOTE]general language of the various subgroups of GF(P^k)[/QUOTE]Which papers or books should I read ?

Same question about:[QUOTE]Frobenius endomorphisms of the (sub-groups of) the higher degree finite fields.[/QUOTE]
[QUOTE]Otherwise, all you are doing is picking out "special cases in disguised form".[/QUOTE]Yes. But it will show people in a clear and elementary way that LLT can be used for other numbers than Mersenne. Many people do not have access to the old papers of Lucas (which do not provide clear and complete proofs ...). I understand that this paper could have been interesting around 1930-1940 and that more modern methods are available now. But I only master this method yet ...

[QUOTE]May I also point out that a LL type test for Fermat numbers is NOT going to be any faster than Pepin's test? For F_n = 2^2^n + 1, both are going to take 2^n modular multiplications/squarings mod F_n.[/QUOTE]I DO agree with you (though E. Lucas talked about a faster test ... but without a clear proof (as usual); look at this [URL="http://tony.reix.free.fr/Mersenne/PrimalityTest4FermatNumbers.pdf"]paper[/URL]), but only about proving that a Fermat is prime.
About proving that a Fermat is not prime, I think that some test based on LLT with cycles could speed up the process. Since Fermat numbers with unknown status are so big, probably the method is mainly useful for Mersennes. But, if a way could be found to split the LLT-on-cycles in several independent steps, F33 could be checked in 1 year instead of about 4000.

About the conjectures : "S(0)=US, S(i+1)=S(i)^2-2 ; Number is prime if S(some k)==US ". Also, I agree that they (if proved some day) will not speed up anything. But, once proved, it could help to have more people looking at these cycles, and not only at the tree of the DiGraph.

Regards,

Tony

[QUOTE=T.Rex;106462]Hi Sir,
Thanks for the suggestion ! I just want to learn. But, since my level of Maths is only "basic", I need time, examples, explanations, ...[/QUOTE]

You need to learn some modern algebra......

[QUOTE]Are you talking of this [URL="http://www.pseudoprime.com/pseudo.html"]Grantham[/URL] ?[/QUOTE]

Yes.

[quote]About the paper of Eric Bach & J. Shallit, do you have a title or a link ?[/QUOTE]

It was in Math. Comp. I don't have the reference handy.

[QUOTE]I DO agree with you. However, do you know about some paper or book that clearly explains this, saying that Pépin or LLT (seed=5 or 6) are equivalent for proving the primality of Fermat numbers, or giving the number (3 or other) to be used for a Pépin's test for Mersennes ?[/QUOTE]

I doubt if such a paper exists.

[QUOTE]If not, you should write such a paper.[/QUOTE]

I would if I could find the time. But it would not be a very significant
result; The existence of a single general test that proves that P is prime
when psi(P) = 2^k [where psi(P) is an appropriate cyclotomic polynomial
in P] is clear from prior work. I don't think that such a general test will
improve practical computation and hence (in my opinion) has limited value.
The Bach/Shallit extension to the P-1/P+1 factoring method had zero
practical use.

[QUOTE]Open the Ribenboim or the Crandall/Pomerance books: they say that Pépins is for N+1 numbers and LLT for N-1 numbers.[/QUOTE]

They are dealing with *special cases* of a more general result. I am sure
that Carl is aware that the Bach/Shallit work could be used to combine
these two tests if he bothers to think about it.

[QUOTE]Which papers or books should I read ?[/QUOTE]

The Bach/Shallit paper and the results of Grantham. You will also need
to learn the general theory of Finite Fields and their structure. I recommend
Lidl & Neidereiter's "Finite Fields" it is superb.

[QUOTE]Same question about:

"Otherwise, all you are doing is picking out "special cases in disguised form".

Yes. But it will show people in a clear and elementary way that LLT can be used for other numbers than Mersenne.[/QUOTE]

I am sure that number theorists already know this. Certainly
the people whose papers I cited realize it.

[QUOTE]Many people do not have access to the old papers of Lucas (which do not provide clear and complete proofs ...).[/QUOTE]

And the methods are ad hoc. Just as the Shallit/Bach paper combined
two special purpose factoring algorithms into one, the Lucas & Pepin
results can be similarly combined.

[QUOTE]I DO agree with you (though E. Lucas talked about a faster test ... but without a clear proof (as usual); look at this [URL="http://tony.reix.free.fr/Mersenne/PrimalityTest4FermatNumbers.pdf"]paper[/URL]), but only about proving that a Fermat is prime.
About proving that a Fermat is not prime, I think that some test based on LLT with cycles could speed up the process.[/QUOTE]

Here, I disagree.

A linear improvement will be useless (i.e. just reducing the number of
multiplications by a constant factor) because even the smallest Fermat
number of unknown status is SO FAR out of range, that no such improvement
will be useful.

[QUOTE]Since Fermat numbers with unknown status are so big, probably the method is mainly useful for Mersennes. But, if a way could be found to split the LLT-on-cycles in several independent steps, F33 could be checked in 1 year instead of about 4000.[/QUOTE]

Once again, your "several independ steps" would just be a disguised way
of doing exponentiations in a finite field, but *IN PARALLEL*.

Finding a new way to do exponential in parallel would be a fantastic
result. But I doubt if one exists.

Bottom line: I doubt very strongly that a method can be found to
reduce the number of multiplications needed in a LL test for Mersenne
Primes *a priori*. **After** testing a given value of M_p, it should
be possible to find a shorter certificate, but it will depend on the number
being tested. I doubt that there is a "universal" generator with a
shorter cycle than we have already.

But it doesn't hurt to look for one.....

[quote=R.D. Silverman;106465]Bottom line: I doubt very strongly that a method can be found to reduce the number of multiplications needed in a LL test for Mersenne Primes *a priori*. **After** testing a given value of M_p, it should be possible to find a shorter certificate, but it will depend on the number being tested. I doubt that there is a "universal" generator with a shorter cycle than we have already.[/quote]
This is most probably true (wide concensus based on elementary considerations), that's why the certainly interesting results presented on the other thread, concerning a "unified scheme" for Mersenne, Wagstaff and Fermat primes, is not really an "advancement" for practical search for prime numbers (as mentioned there) [URL="http://en.wikipedia.org/wiki/Per_se"][I]per se[/I][/URL].

However, I strongly believe that it should be "relatively easy" to find (at least statistically) more efficient methods than the LL test for showing NON-primality of (at least some) Mp, which today are tested by GIMPS using the classical LL test. And almost all of GIMPS' work is about showing NON-primality (except for roughly 1 in a million)...
And cumulating results on the structure of the LL type proofs could give us some idea of where or what we should look for.

[QUOTE=akruppa;30948]In Williams P+1 factoring, whether your starting element s has order p+1 or p-1 depends on whether s^2-4 isn't or is a qudaratic residue (mod p). I believe the same is happening here.

[/QUOTE]

A note:

Again, something is happening in disguise. If s^2-4 is a non-residue, then
s is in the TWISTED sub-group. If s^2-4 is a residue, then s is in Z/pZ*
(so that the order is p-1, not p+1 and hence Pollard p-1 is being run instead of p+1). The reciprocity test tells WHICH subgroup s is in. However, since
you don't know p in advance, you just select s at random. It will be in the
group of order p+1 half the time.

[QUOTE=R.D. Silverman;106465]> Here, I disagree.
A linear improvement will be useless (i.e. just reducing the number of multiplications by a constant factor) because even the smallest Fermat number of unknown status is SO FAR out of range, that no such improvement will be useful.[/QUOTE]Are you talking about: "though E. Lucas talked about a faster test" ? He talked (with no proof ...) about a 25% improvement. Not so bad: instead of 4000 years, you need only 3000 :wink: .
About the rest of your comments, thanks. I'll need time to digest them ...
T.

[quote=T.Rex;106462]About the paper of Eric Bach & J. Shallit, do you have a title or a link ?[/quote]
is it this :
E. Bach and J. Shallit. Factoring with cyclotomic polynomials. Math. Comp., 52:201--219, 1989.

Available online: [url]http://dx.doi.org/10.2307/2008664[/url]

[URL="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.299.3682&rep=rep1&type=pdf"]Primality Criteria for Specific Classes of Proth Numbers[/URL]

[QUOTE=primus;378791][URL="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.299.3682&rep=rep1&type=pdf"]Primality Criteria for Specific Classes of Proth Numbers[/URL][/QUOTE]

Your post consists of unnecessary hype. As posted, it makes it appear
as if the content of the paper discusses PROVED results.

It should be titled:

[b]CONJECTURED[/b] Primality Criteria for Specific Classes of Proth Numbers


Proth numbers are easy to prove prime anyway because the full factorization
of N-1 follows immediately from the form of the number.

Even if the above conjectures are true, they add very little to the practical art for proving Proth numbers are prime.

[QUOTE=R.D. Silverman;106443]They can be extended to primes for which ANY cyclotomic polynomial in P = 2^k[/QUOTE]

I have a fairly strong suspicion (though I suspect it would need Alan Baker-style techniques to prove it) that no such primes exist; indeed, that no numbers exist for which polcyclo(k,n) is a power of two for k>2, n>0.

[QUOTE=fivemack;378883]I have a fairly strong suspicion (though I suspect it would need Alan Baker-style techniques to prove it) that no such primes exist; indeed, that no numbers exist for which polcyclo(k,n) is a power of two for k>2, n>0.[/QUOTE]

Certainly for any given degree for the cyclotomic polynomial
there will be at most finitely many. (via Siegel's Thm)

[QUOTE=fivemack;378883]I have a fairly strong suspicion (though I suspect it would need Alan Baker-style techniques to prove it) that no such primes exist; indeed, that no numbers exist for which polcyclo(k,n) is a power of two for k>2, n>0.[/QUOTE]

I think you want n>1, else you have lots of examples.

[QUOTE=R.D. Silverman;378873]Your post consists of unnecessary hype. As posted, it makes it appear
as if the content of the paper discusses PROVED results.

It should be titled:

[b]CONJECTURED[/b] Primality Criteria for Specific Classes of Proth Numbers


Proth numbers are easy to prove prime anyway because the full factorization
of N-1 follows immediately from the form of the number.

Even if the above conjectures are true, they add very little to the practical art for proving Proth numbers are prime.[/QUOTE]

[URL="https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxwZWRqYXByaW11c3xneDoyN2Q1OGI1N2ZhMGY5MWZj"]Conjectured Polynomial Time Primality Tests for Numbers of Special Forms[/URL]