20181222, 22:57  #364 
"Daniel Jackson"
May 2011
14285714285714285714
277_{16} Posts 
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 20122016, and fix the low page requests too.

20190130, 13:54  #365  
Sep 2002
Vienna, Austria
219_{10} Posts 
Quote:


20190131, 14:47  #366 
May 2018
43 Posts 
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. 
20190407, 02:22  #367 
Sep 2003
3^{2}×7×41 Posts 
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.
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. 
20190407, 03:51  #368  
Sep 2003
3^{2}×7×41 Posts 
Quote:
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. 

20190407, 07:15  #369 
Sep 2003
3^{2}·7·41 Posts 
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).

20190407, 17:02  #370 
Sep 2003
A17_{16} Posts 
And the same problem for (11^n+1)/12 for exponents 7681, 7757, 8369, 12967, 13037, 16573, 17837, 19553, 20887

20190408, 08:23  #371 
Mar 2018
3×43 Posts 
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). Last fiddled with by DukeBG on 20190408 at 08:31 
20190408, 08:57  #372  
Sep 2003
3^{2}×7×41 Posts 
Quote:
Clicking on the "728,117" link (or whatever the number is by the time you read this), indicates that it's a "MillerRabin'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 socalled "PRPs" that haven't. Last fiddled with by GP2 on 20190408 at 08:59 

20190408, 09:14  #373  
Jun 2003
2×3^{2}×269 Posts 
Quote:


20190408, 13:35  #374  
Feb 2017
Nowhere
23×181 Posts 
Quote:
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 N1 = (p1)*(q+2), so b^(N1) is a power (an odd power) of b^(p1). Thus, b^(N1) == 1 (mod p), and is either 1 or 1 (mod q). If it is 1 (i.e. b is a quadratic nonresidue (mod q)) then b^(N1) =/= 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 nonresidue (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 RabinMiller, we require b^((N1)/2) == 1 or 1 (mod N). We have b^((N1)/2) is an odd power of b^((p1)/2)), so is 1 (mod p) if b is a quadratic residue (mod p) and 1 (mod p) if b is a nonresidue (mod p). In the first case, we fool RabinMiller if b^((p1)/2) == 1 (mod q) [i.e. b is a 4th power residue (mod q)]. In the second case, we "fool" RabinMiller if b is not a 4th power residue (mod q). So it looks like, overall, for such an N, it's not too hard to "fool" RabinMiller  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" RabinMiller. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A suggestion for factordb.  enzocreti  FactorDB  10  20210105 19:49 
Extending Factordb  carpetpool  FactorDB  6  20170123 11:04 
FactorDB PRP's  smh  FactorDB  231  20150728 02:30 
bugged sequence in factordb  firejuggler  Aliquot Sequences  2  20100615 14:03 
FactorDB question  Raman  Factoring  15  20100128 10:24 