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

[R.D. Silverman]

Originally Posted by T.Rex

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: http://tony.reix.free.fr/Mersenne/PR...MBERSarXiv.pdf

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: http://arxiv.org/auth/endorse.php?x=RD7EN8
If that URL does not work for you, please visit http://arxiv.org/auth/endorse.php 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 tony.reix@XXXXXXXX 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.

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

[R.D. Silverman]

Originally Posted by R.D. Silverman

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>

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.

[T.Rex]

Hi Sir,

Originally Posted by R.D. Silverman

May I suggest to all of you who ...

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 Grantham ?
About the paper of Eric Bach & J. Shallit, do you have a title or a link ?

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

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.

general language of the various subgroups of GF(P^k)

Which papers or books should I read ?

Same question about:

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

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

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.

I DO agree with you (though E. Lucas talked about a faster test ... but without a clear proof (as usual); look at this paper), 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

[R.D. Silverman]

Originally Posted by T.Rex

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

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

Are you talking of this Grantham ?

Yes.

About the paper of Eric Bach & J. Shallit, do you have a title or a link ?

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

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 ?

I doubt if such a paper exists.

If not, you should write such a paper.

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.

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

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.

Which papers or books should I read ?

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.

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.

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

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

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.

I DO agree with you (though E. Lucas talked about a faster test ... but without a clear proof (as usual); look at this paper), 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.

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.

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.

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

[m_f_h]

Originally Posted by R.D. Silverman

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.

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) per se.

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.

[R.D. Silverman]

Originally Posted by akruppa

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.

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.

[T.Rex]

Originally Posted by R.D. Silverman

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

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 .
About the rest of your comments, thanks. I'll need time to digest them ...
T.

[m_f_h]

Originally Posted by T.Rex

About the paper of Eric Bach & J. Shallit, do you have a title or a link ?

is it this :
E. Bach and J. Shallit. Factoring with cyclotomic polynomials. Math. Comp., 52:201--219, 1989.

Available online: http://dx.doi.org/10.2307/2008664

[primus]

Primality Criteria for Specific Classes of Proth Numbers

[R.D. Silverman]

Originally Posted by primus

Primality Criteria for Specific Classes of Proth Numbers

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:

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

[fivemack]

Originally Posted by R.D. Silverman

They can be extended to primes for which ANY cyclotomic polynomial in P = 2^k

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.