Other Factordb Problems

[Dr Sardonicus]

Originally Posted by GP2

The FactorDB status page show a count of 728,117 (currently) for "Probable primes that failed primality proof or had a factor". Wow.

Clicking on the "728,117" link (or whatever the number is by the time you read this), indicates that it's a "Miller-Rabin's probabilistic test (order 10 at least)".

If you picture the concept of a PRP as being "overwhelmingly likely to be an actual prime", it's alarming to see so many very weak pseudoprimes. FactorDB should distinguish somehow between true PRPs that have had a "Check base" done to at least two bases, and the so-called "PRPs" that haven't.

I don't understand how Rabin-Miller is being implemented on these numbers. They all appear to be of the form

n = p * q, p == 3 (mod 4), q = 2*p - 1 also prime.

The condition that b^(n-1) == 1 (mod n) is that kronecker(b, q) = +1, a condition that is never satisfied by b = 2, and is generally satisfied by about half of the bases b.

The further condition that b^((n-1)/2) == 1 or -1 (mod n) is that kronecker(b,p) = (b/q)₄ (4-th power residue character, 1 or -1 since kronecker(b,q) = +1, congruent to Mod(b,q)^((q-1)/4)).

This condition appears to eliminate about half the bases b for which kronecker(b,q) = +1. So, for r rounds, one would expect perhaps a 1/4^r probability of n failing to test as composite.

I ran ispseudoprime(n,k) for k = 1 to 4 on the first 35 numbers on the list. This does Rabin-Miller with k randomly chosen bases. Only a few failed to test as composite for any k, and only 2 or 3 for more than one k.

All of the 35 numbers tested as composite for every run with k = 4.

I also checked the conditions for prime bases b up to 100, 1000, and 2000. In each case, about 1/4 of the prime bases b satisfied the conditions for n failing to test as composite.

So it seems to me that, in order for n to fail to test composite by Rabin-Miller for at least ten bases, the bases almost have to be chosen rather carefully to insure that outcome.

Unless, of course, the "ten rounds" were all done to the same base, or powers of one base...

[GP2]

Originally Posted by Dr Sardonicus

I don't understand how Rabin-Miller is being implemented on these numbers.

Who knows. Maybe some of them are historical, and a different algorithm was used in the past. The number 728,117 hasn't increased in the past couple of days.

The ones I'm seeing definitely fit the category of (b^n+1)/(b+1) for odd b. Apart from the ones already mentioned, for b=13 there was n=8669, 19993.

[DukeBG]

That page is very "historical". Those small numbers are from years ago. The weak PRP's I was talking about were much higher digit counts and thus not seen on that page.

Here are some picked from some different parts of my logs.
http://factordb.com/index.php?id=1100000000933198724
http://factordb.com/index.php?id=1100000000851496321
http://factordb.com/index.php?id=1100000000851706313
http://factordb.com/index.php?id=1100000000851982326
http://factordb.com/index.php?id=1100000001177551445
http://factordb.com/index.php?id=1100000001137959890
http://factordb.com/index.php?id=1100000001197237994
http://factordb.com/index.php?id=1100000001109177324
http://factordb.com/index.php?id=1100000001254036805
http://factordb.com/index.php?id=1100000001224177583
http://factordb.com/index.php?id=1100000001269922385
http://factordb.com/index.php?id=1100000001109152306

[R. Gerbicz]

Originally Posted by Dr Sardonicus

Actually, looking at the factorizations, it's not too hard to see what's going on. The first several I looked at had the factorization

N = p * q, where

p == 3 (mod 4) is prime, and

q = 2*p - 1 is also prime.

Yes, I've searched only this form, there are other similar forms, but this is the best.

Originally Posted by GP2

The FactorDB status page show a count of 728,117 (currently) for "Probable primes that failed primality proof or had a factor". Wow.

Clicking on the "728,117" link (or whatever the number is by the time you read this), indicates that it's a "Miller-Rabin's probabilistic test (order 10 at least)".

If you picture the concept of a PRP as being "overwhelmingly likely to be an actual prime", it's alarming to see so many very weak pseudoprimes. FactorDB should distinguish somehow between true PRPs that have had a "Check base" done to at least two bases, and the so-called "PRPs" that haven't.

Maybe I've discovered 98% of those numbers, check out for the record order:

https://www.mersenneforum.org/showpo...postcount=1546

Note that we know the bases in the Miller-Rabin tests if you check out the gmp source code,
so this is not just submitting randomly such p*(2*p-1) numbers, and hoping for a luck; in fact I've submitted
the number only if it has order>=10.

Also note that the bases depends on n, so not fixed! And before the Rabin tests there is also
a Fermat test for the fixed(!) base=210. And be careful: older gmp versions used different generation
for the random bases, but in the recent versions they haven't changed it.

Since the bases are not fixed, it could be very hard/impossible to construct large order numbers,
so to do an Arnault attack: http://www.ams.org/journals/mcom/199...-1260124-2.pdf .

[Dr Sardonicus]

Originally Posted by R. Gerbicz

<snip>
Note that we know the bases in the Miller-Rabin tests if you check out the gmp source code,
so this is not just submitting randomly such p*(2*p-1) numbers, and hoping for a luck; in fact I've submitted the number only if it has order>=10.
<snip>
Also note that the bases depends on n, so not fixed!

I would guess that about 1 in 4^10, or about 1 in a million, of these numbers would "pass" ten rounds of Rabin-Miller; also, about half (those for which 210 is a quadratic residue mod q) would pass the initial Fermat test. So maybe 1 in 2 million might make the "ten rounds" list?

Alas, I doubt trying to read source code would tell me much, except that I'm not very good at reading code, which I already know...

But the fact that the bases depend on n, rather than being fixed, is new to me. It would be interesting to see the "lucky" bases that let some of the n's "pass" so many rounds of Rabin-Miller.

If the fixed base for the Fermat test had been taken to be 2 instead of 210, the list would have been much shorter.
:-D

[Dr Sardonicus]

I found Thomas R. Nicely's page GNU GMP mpz_probab_prime_p pseudoprimes which has a few "high-order" Miller-Rabin PRP composites. It looks like order-10 and higher ones were being found as early as 2004.

[R. Gerbicz]

Originally Posted by Dr Sardonicus

I would guess that about 1 in 4^10, or about 1 in a million, of these numbers would "pass" ten rounds of Rabin-Miller; also, about half (those for which 210 is a quadratic residue mod q) would pass the initial Fermat test. So maybe 1 in 2 million might make the "ten rounds" list?

Yes, in each order=o I had roughly 4 times less numbers than on order=o-1.

Using fixed base is just dangerous, see Arnault; probably this was the reason why they
are using random base, an easier case shows why we can almost eliminate the fixed base=210 for Fermat test
in my search:

very basic, with Fermat's little theorem and Euler's criterion:

n=p*q=p*(2*p-1)
n-1==0 mod (p-1) ---> 210^(n-1)==1 mod p
n-1==p-1==(q-1)/2 mod (q-1) ---> 210^(n-1)==210^((q-1)/2)==(210/q) mod q

so n is Fermat pseudoprime iff (210/q)=1 and this depends only on p%420 (we already know p%4=3).

Note that this calculation is independent from the base and since
calculation of (base/q) is faster than powmod it is better to
get first these, because if (base/q)=-1 then n isn't even a Fermat
pseudoprime so it can't be a strong pseudoprime for base. And you
can do this with the first ten random bases (with early exit), if
you want to see only order>=10.

[Puzzle-Peter]

I am having problems uploading a certificate. It is not absurdly large (32MB unzipped) but somehow it does not work. Everything seems fine but then the upload certificate page appears again and there is no sign of the certificate being processed or even stored. I tried zipped and unzipped.

[EdH]

I haven't been able to send zipped certificates since the last large down-time, but I was sending individual OK. I just tried one that had already been sent and got "Number already proven." This is what I expected.

I'm using Primo 4.3.0 LX64.


Edit attempt: "The server is too busy at the moment. Please try again later."
fingers drumming...
"The server is too busy at the moment. Please try again later."

fingers drumming...
"The server is too busy at the moment. Please try again later."

fingers drumming...
I wnet ahead and submitted a new certificate and all went as expected for unzipped. Since I haven't been able to send zipped, I didn't try this time.

[Puzzle-Peter]

I sent it to Markus via email and he plugged it into the db seemingly without problems. I do not understand.

[EdH]

Originally Posted by Puzzle-Peter

I sent it to Markus via email and he plugged it into the db seemingly without problems. I do not understand.

It's good you got it submitted, but I wonder about the issue. I've not contacted Markus about my zipped files trouble. As far as I've seen elsewhere someone has been doing zipped without issue.