Other Factordb Problems

[Stargate38]

I've noticed the reduced limits as well. 550 seconds of CPU time per hour isn't enough, especially when I'm reloading Aliquot sequences that haven't been reloaded since the DB lost track of all the sequences. @Syd: Please set my CPU limit back at 2000 seconds/hour, like it was from 2012-2016, and fix the low page requests too.

[wpolly]

Originally Posted by Syd

I think I figured out why some numbers are causing trouble, are not accepting factors or show up as PRP incorrectly - these numbers are listed in multiple tables, like PRP and C at the same time.
Not sure how this happened, I guess when the disk was full or after one of the server crashes.

Its a total of 120944 numbers. I'll delete these now, fingers crossed. Backup is at hand.

Hey Syd, how's it going with the duplicate-removal? Looks like the offenders (e.g. 1100000000900935563) are still in the database...

[ricky]

Hi, I noticed that in aliquot sequence 3^108, in factordb, the 1575th term is wrong. Can somebody correct it?

It should be 15540084064757285981320 instead of 15539970862145288285320.

[GP2]

All of these were listed as PRP in FactorDB until today, when I simply ran a "Check base" for base 3 in FactorDB itself, and it flipped them to composite.

• (5^39733+1)/22409418
• (5^39511+1)/3225520002
• (5^38933+1)/76323459122538
• (5^38923+1)/414296418
• (5^19991+1)/12756830681778
• (5^19267+1)/1565351557327938
• (5^18457+1)/2530011738
• (5^11777+1)/1644043903491449888682
• (5^11519+1)/218565799407762
• (5^10369+1)/796008769874202
• (5^8731+1)/705220338
• (5^7873+1)/1483934538
• (5^6301+1)/95690599873291154171802

and 6659, 6701, 6967, 7717, 8713, 9631, 10009, 10037, 10267, 11047, 11083, 12323, 12329, 12347, 14173, 14327, 14747, 14779, 15199, 16001, 16363, 16729, 16937, 17183, 17489, 19543, 19759, 19891, ... and many, many more fake PRPs... up until the 40k range where they seem to peter out.

And that's just for prime exponents, I didn't check composites.

[GP2]

Originally Posted by GP2

• (5^8731+1)/705220338

I reported the factors 70304107441 and 924285488818604234209, which are actually old factors that were somehow lost by FactorDB at some point.

That caused the new cofactor (5^8731+1)/45825969548191617905021916649294475599122 to appear as PRP, until I did Probable prime Check base = 3 to cause it to reset to Composite.

Something is definitely wrong with FactorDB's automated PRP testing for (5^n+1)/6

For the exponent 7873 I reported the factors 320773148153561 and 5510953013247203, however those did not make the new cofactor to be a false PRP.

[GP2]

The same problem happened with bogus PRPs for (7^n+1)/8 and exponents 9319, 10589, 12979, 14561, 14653, 14813, 23563, 23899, 24907, 25121, 29179, 32027, 32531 (only checking prime exponents, and up to 50k).

[GP2]

And the same problem for (11^n+1)/12 for exponents 7681, 7757, 8369, 12967, 13037, 16573, 17837, 19553, 20887

[DukeBG]

As I said before, there were thousands of these for base 2 that I "poofed" by the "check" procedure with base 3. They kept rarely appearing (and still occasionally do) as I was adding any factors (including algebraic) for mersenne numbers (with composite exponents) for small enough numbers (below ~20K dd i guess).

The main problem with them they don't turn into C when adding factors, even though the input field is available. You only have to "check base" for them to turn into C and then you'll be able to successfully add a factor. When Jonathan Crombie (myfactors.mooo.com) was adding his factors into FDB in about December 2018, he (unknowingly to him) ran into this. I was checking his base 2 factors against FDB (that is part of my setup) and there was an exponent where FDB cofactor turned into PRP and the next factor for that exponent wasn't added to the database.

Running a check base 3 call has long became part of my scripts for interacting with FDB. I have a file of "true" PRPs that survive that (and don't need check base again). I have never found any that "survived" base 3, but became composite after base 5 or base 7 or any other base check (no carmichael numbers).

I believe (but never tested) they are actually weak pseudoprimes. Even though I've been told before that FDB is supposed to be using PFGW, I don't think it is giving those results, something else is being used to quickly test cofactor after adding factors. I don't think they ever appeared from "assigning number for a PRP test" – available for U numbers. (which i am convinced is a PFGW queue).

[GP2]

Originally Posted by DukeBG

I believe (but never tested) they are actually weak pseudoprimes. Even though I've been told before that FDB is supposed to be using PFGW, I don't think it is giving those results, something else is being used to quickly test cofactor after adding factors.

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.

[axn]

Originally Posted by DukeBG

Even though I've been told before that FDB is supposed to be using PFGW, I don't think it is giving those results, something else is being used to quickly test cofactor after adding factors. I don't think they ever appeared from "assigning number for a PRP test" – available for U numbers. (which i am convinced is a PFGW queue).

FDB will automatically PRP test (I believe, base 2 PRP test done using PFGW) any unknowns with less than 20000 digits. Only the ones >= 20000 digits will be available for "Assign to PRP test". (actually, if you dump a whole bunch of smaller unknowns, it will take FDB a while to do the PRP on all of it -- in the meantime, they will have the "assign" option available).

[Dr Sardonicus]

Originally Posted by GP2

The [URL="http://factordb.com/status.php"]<snip>
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)".

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.

This means that N == 3 (mod 4), and

q - 1 = 2*(p - 1), so that, for any base b,

znorder(Mod(b,N)) divides q - 1 = 2*(p - 1).

Now N-1 = (p-1)*(q+2), so

b^(N-1) is a power (an odd power) of b^(p-1).

Thus, b^(N-1) == 1 (mod p), and is either 1 or -1 (mod q). If it is -1 (i.e. b is a quadratic non-residue (mod q)) then b^(N-1) =/= 1 (mod N), so N is immediately detected as composite.

Curiously, with p == 3 (mod 4), we have 2*p == 6 (mod 8) and q == 5 (mod 8), so that 2 is a quadratic non-residue (mod q). Thus, such an N is always detected as composite with a simple pseudoprime test to the base b = 2.

In order to "fool" the simple pseudoprime test to base b, b must be a quadratic residue (mod q). For Rabin-Miller, we require b^((N-1)/2) == 1 or -1 (mod N). We have

b^((N-1)/2) is an odd power of b^((p-1)/2)), so is 1 (mod p) if b is a quadratic residue (mod p) and -1 (mod p) if b is a non-residue (mod p).

In the first case, we fool Rabin-Miller if b^((p-1)/2) == 1 (mod q) [i.e. b is a 4-th power residue (mod q)]. In the second case, we "fool" Rabin-Miller if b is not a 4-th power residue (mod q).

So it looks like, overall, for such an N, it's not too hard to "fool" Rabin-Miller -- as long as you avoid the base b = 2.

If p == 1 (mod 4) then 2*p - 1 == 1 (mod 4) also, so N == 1 (mod 4), and it becomes correspondingly more difficult to "fool" Rabin-Miller.