A (new) old, (faster) slower mersenne-(primality) PRP test

[paulunderwood]

Originally Posted by axn

This is all the explanation that is needed for the timing differences.

Now let's suppose that in practical implementation, getting rid of the subtraction affords us some saving. But note that LL test uses p-2 iteration while this test uses p-1 iteration -- 1 whole extra iteration. Oops. That right there will wipe out any savings.

Early iterations can be precomputed. Most importantly, Derrick Lehmer's algorithm is a proof.

[Batalov]

Originally Posted by boldi

I copy the
conjecture from my first post at this place, and please read it carefully
(but not seriously ;-)

What is this, a proof by repetition? Repeat your statement until everyone walks away - and you win? No. You don't win by repetition.

Originally Posted by boldi

And again: This is not the Fermat test.

Let me get this straight, and in terms that you will be able to follow.

You put a shirt in a washing machine and say loudly: "this is a washing machine, and here's how it works". Everyone agrees. Yes, this is a washing machine. We've seen it before. It's been known for a few centuries.

You put sneakers in a washing machine and say loudly: "this is not a washing machine, it is a completely new machine, and here's how it works". Some people even gather around and start asking questions: "how does this wonderful new boldi machine works?"

It is still a washing machine, the same old washing machine - its name doesn't depend on what you put in it. It makes things clean. It doesn't make them new. Even if the things look new when they come out of the washing machine, they are in reality not new. Just clean.

If you proved that sneakers (exactly sneakers, but not anything else) come out of the machine not just clean, but new, then it would have been an achievement. Well? You didn't. Hence, it is still the same ol' washing machine.

To your last retort ("but I was first to make this conjecture! It is mine! All that's left is to prove it"), - nope, even that is not new.

It is also not faster. And just in case you don't understand the subtleties, the opposite of "faster" (>) is not "slower" (<). It is "not faster" (<=). It includes "equally fast"; ever heard of the "=" sign? The 3-PRP is exactly as fast as the LL test, when both are implemented correctly. If you don't know what this statement means, or if it is true, or what "implemented correctly" means (I'll give you a hint: it doesn't include running things in Pari, BASIC, or even in plain C) - it is a bit of a problem. Your problem, to be precise.

The second post already told you that. This thread ended with the second post. Everything below it is just idle coffee room chatter.

[boldi]

Originally Posted by Batalov

What is this, a proof by repetition? Repeat your statement until everyone walks away - and you win?

Please, please, please.

Calm down. Please realize, that there is no counterexample.

The conjecture is still valid.

In the data that Mayer has posted, you will not find a counterexample. He
shows only some factorizations on base 3 done in 1997. And if you read
carefully, Mayer does also not claim to have a counterexample. It was only
a little bit a flash grenade ;-) but it was enough, that someone was
destroying the headline of the thread.

You?

If you are the opinion, that the conjecture is disproved, please show where it was done.

Everything below it is just idle coffee room chatter.

If you want, we can also drink a cup of tea.


Greetings
boldi

[Batalov]

Calm down, boldi. ;-)

boldi's Profile
Total Posts: 14
Posts Per Day: 7.01 ! (and all are essentially a repetition of the first post)

Stop putting your problems on others. "Calm down". You are funny.

Instead, go to any shopping mall, stand next to a washing machine and tell everyone that you invented it. Do you understand the analogy?
Just answer: yes or no?

[CRGreathouse]

Originally Posted by boldi

Please realize, that there is no counterexample.

The conjecture is still valid.

In the data that Mayer has posted, you will not find a counterexample. He
shows only some factorizations on base 3 done in 1997. And if you read
carefully, Mayer does also not claim to have a counterexample. It was only
a little bit a flash grenade ;-) but it was enough, that someone was
destroying the headline of the thread.

You?

If you are the opinion, that the conjecture is disproved, please show where it was done.

Batalov's claim was not that he had a counterexample, but rather that you had not proved that your method works. There are plenty of things we believe to be wrong even though we don't have a counterexample at hand.

[science_man_88]

We are essentially working within the mersennes completely and your conjecture is saying only the first of the following works and only for prime exponents:

1. for odd Mersenne exponents and;
2. for even exponents

you must prove this if you are going to assert it's truth over and over.

[henryzz]

Originally Posted by ewmayer

The "can we stay in FFT space?" issue is the same for more or less all FFT-based modmul applications; the precise form of the modulus is secondary. Short answer (longer one already given above): no, as the reduction in input size needed to permit this more than offsets the savings resulting from skipping the iFFT for one or more steps.

==================

BTW, it should be clear to everyone by now that the OP's test is just an Euler-prp test in (very slight) disguise - the extra mul-by-the-base-used is slightly useful in that context since it eliminates the muls-by-3 which would otherwise be needed, but again:

[1] Not proven rigorous for M-primes - in fact there appear multiple good reasons pointing to "probabilistic" for such numbers, although the sparseness of the M(p) makes an explicit false-positive a low-probability event;

[2] Even were it a rigorous prime test, it's no faster than LL, timings based on scripting languages like Pari notwithstanding.

=================

Lastly, I dug out the old Fortran-90 code I used back in '97 to run base-3 Euler-prp tests on a bunch of M(p) with known factors - I was using the Euler residue to perform a subsequent Suyama-like prp test of the large cofactors, my runs turned up a half-dozen such prp cofactors which are listed somewhere in the old Mersenne mailing-list archives of the time. The largest of those was ~10000 digits; the largest I was actually able to prove prime (with Francois Morain's ECPP code and help) was the cofactor of M(7331), which gets a mention in Crandall & Pomerance as it was at the the time an ECPP record.

Ah, I grepped for "7331" in my old code-and-textfile archive and found the list - 10 previously-unknown prp Mersenne cofactors, the smallest 4 of which were proven prime via ECPP:

p        factorization of M(p)
-----        -------------------------------
4751    268982617.3274778783.629530076753.1507074535068001.81630665742097.    p1372
5689    919724609777.    p1701
6883    1885943.2043031664890199.    p2051
7331    458072843161.    p2196

7673    184153.13918823.    prp2298
14561    8074991336582835391.    prp4365
17029    418879343.    prp5118
28759    226160777.    prp8649
28771    104726441.    prp8653
32531    65063.25225122959.    prp9778

BTW, if anyone wants to have a crack at the top 6 - after first checking whether anyone else has proven them yet - have at it using Primo or whatever the current top dog in rigorous prime proving is. (I would appreciate some form of acknowledgment by way of having been the discoverer-of-prp-status, though.)

Here is the salient snip from the comment block at top of the source: Note that the main practical item of relevance to the current thread is the fact that the muls-by-3 are trivially absorbed into the IBDWT weights work which bookends each FFT-based modsquare:

Code to test compositeness of Mersenne numbers M(p)=2^p-1, using arbitrary-
precision array-integer arithmetic and a base-3 Euler pseudoprime test;
or to test the cofactor of a prime-exponent Mersenne number with one or
more known factors (which must be < 2^113 in size) for probable-primality.

Accomplishes the Mersenne-mod squaring via the weighted discrete
Fourier transform technique of Crandall and Fagin (Mathematics of
Computation, vol. 62, p.305, Jan 1994).

If a prime exponent p gives a result which is flagged as a probable
prime, run (don't walk) a Lucas-Lehmer test to be sure.

If M(p) has >= 1 known factors F1, F2, ... , FN with product F = F1 X F2 X FN,
(note that only the individual factors must be < 2^113; the product can be
arbitrarily large, although N > 10 requires the parameter NFACT_MAX to be increased
the Euler base-3 residue is calculated, an extra iteration performed, and the
resulting "plus one" residue used to perform a Suyama cofactor analysis
(cf. H. Riesel, "Prime Numbers and Computer Methods for Factorization," 2nd ed.,
1994, Birkha"user Verlag, p. 102.) Any cofactors M/F that
pass the test are probable primes, in the sense that they are simultaneously
Fermat pseudoprimes to base 3^F and Euler pseudoprimes to base 3^(2F).

Gzipped source is attached.

This isn't being cooperative in compiling for me using cygwin's gfortran.
I was getting errors with qint so I followed the suggestion in the code. I now mostly get the following type of error:

mersenne_cofactor.f90:286.60:

 print'(a,i4,a,f35.0)','factor',i,'=',int(qfactor(i)/2,kind=r16) !* if your com
                                                            1
Error: Invalid kind for INTEGER at (1)

I don't know fortran and don't have time to spend learning currently. Is there some quick fixes to get it to compile?

[ewmayer]

Originally Posted by R.D. Silverman

However. The 1st routine did 131 thousand single precision subtractions
not done by the second routine. The claim is that the 2nd routine was 4 secs
(about 1/2%) faster as a result.

Does anyone seriously think that 131 thousand single precision subtractions
takes 4 seconds????? Each operation takes a single clock!

The -2 is not even that (tiny bit) costly - one always needs to init the carryin to the carry chain to *something*, and init = -2 is no slower than init = 0, as far as I can tell.

=================

Originally Posted by henryzz

Error: Invalid kind for INTEGER at (1)[/code]I don't know fortran and don't have time to spend learning currently. Is there some quick fixes to get it to compile?

Hi, Henry:

And I have no time to try to relearn the various intricacies of F90 - just note that my old F90 stuff was all developed on one kind of platform (DEC Alpha, using the DEC F90 compiler), so if you want to get a quick idea what may be awry, your best bets are

[a] Repost the gzipped source to an online Fortran board along with your errors and see if a quick fix emerges;

[b] Try one or more alternate F90 compilers / hardware platforms.

Sorry, wish I had time to be of more help at the moment, but don't.

[ewmayer]

Small clarification, since the OP first states one thing, then actually computes another, and there are several distinct classes of probable-primality tests in play:

Originally Posted by boldi

3^(M-1) ≡ 1 mod M

That is just a base-3 Fermat pseudoprime test. No reason to expect it to be rigorous for M an odd-prime-exponent Mersenne number. Oddly, the OP is clearly acquainted with Fermat's "little" theorem, but despite that goes on to claim rigor for the test applied to prime-exponent Mersennes. "I only need a proof" - that assumes there *is* a proof. The only missing thing is ... a proof. And what the OP actually computes is something different:

Originally Posted by axn

I think the OP realizes this -- hence his actual calculation uses 3^(N+1)/2 == -3 (mod N). which requires only repeated squarings

And this is the "Euler pseudoprime test in slight disguise" I mentioned - start with the orthodox Euler pseudoprime criterion (I replace axn's N with M here to make notation match that in the OP:

3^(M-1)/2 == -1 (mod M)

Again no reason to expect this crterion to be rigorous for Mersennes, since those lack the key property which make the test rigorous for Fermat numbers. The reason we can restrict ourselves to -1 for the Legendre symbol on the RHS is that the base 3 is a quadratic non-residue modulo the stated class of moduli (you can see the 1997 archived code I posted also uses this quadratic nonresiduacity property and tests the powering residue against -1):

Originally Posted by R.D. Silverman

OK. He computed 3^(n-1) in a disguised way. BTW, this disguised
way uses the fact that 3 is a quadratic non-residue (compute the Jacobi
symbol) and utilizes Euler's criterion for a non q.r. Instead of 3^(2^n-1),
the computation was 3^2^n followed by a (somewhat) hidden post-multiply
to get rid of the (-1) in the exponent. It's actually a nice way to do it.

Now take the above Euler pseudoprime criterion and multiply by the base to get what is actually computed:

3^(M+1)/2 == -3 (mod M),

which works so long as 3 < M, which is true for all Mersennes with exponent p > 2.

As Bob notes that last bit is actually a nice trick for the case of Mersenne moduli since it does those the same thing that occurs in the orthodox Euler test for Fermat numbers: it leads to just a single lit bit in the exponent, and thus eliminates any scalar-muls-by-base which are needed in left-to-right binary powering whenever an intermediate bit in the binary expansion of the powering exponent = 1. As I noted such scalar muls can be easily dealt with in practice by folding them into the carry step of each iteration, but it's more elegant to do the above way.

Now, why am even bothering with any of this, since we know we're dealing with a criterion which has no complexity advantages over LL and has no proof of rigor for the moduli in question? The reason is that I can't help but think that had the OP done his homework and presented it in a form more like that above rather than making grand claims and evidencing that peculiar combination of ignorance and arrogance which is the classic hallmark of the crank, the resulting thread would surely have had a very different tone than the one which actually ensued.

Off to bed...