mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2018-12-22, 22:57   #364
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

27716 Posts
Default

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.
Stargate38 is offline   Reply With Quote
Old 2019-01-30, 13:54   #365
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

21910 Posts
Default

Quote:
Originally Posted by Syd View Post
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...
wpolly is offline   Reply With Quote
Old 2019-01-31, 14:47   #366
ricky
 
May 2018

43 Posts
Default

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.
ricky is offline   Reply With Quote
Old 2019-04-07, 02:22   #367
GP2
 
GP2's Avatar
 
Sep 2003

32×7×41 Posts
Default

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.
GP2 is offline   Reply With Quote
Old 2019-04-07, 03:51   #368
GP2
 
GP2's Avatar
 
Sep 2003

32×7×41 Posts
Default

Quote:
Originally Posted by GP2 View Post
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 is offline   Reply With Quote
Old 2019-04-07, 07:15   #369
GP2
 
GP2's Avatar
 
Sep 2003

32·7·41 Posts
Default

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 is offline   Reply With Quote
Old 2019-04-07, 17:02   #370
GP2
 
GP2's Avatar
 
Sep 2003

A1716 Posts
Default

And the same problem for (11^n+1)/12 for exponents 7681, 7757, 8369, 12967, 13037, 16573, 17837, 19553, 20887
GP2 is offline   Reply With Quote
Old 2019-04-08, 08:23   #371
DukeBG
 
Mar 2018

3×43 Posts
Default

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 2019-04-08 at 08:31
DukeBG is offline   Reply With Quote
Old 2019-04-08, 08:57   #372
GP2
 
GP2's Avatar
 
Sep 2003

32×7×41 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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.

Last fiddled with by GP2 on 2019-04-08 at 08:59
GP2 is offline   Reply With Quote
Old 2019-04-08, 09:14   #373
axn
 
axn's Avatar
 
Jun 2003

2×32×269 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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).
axn is offline   Reply With Quote
Old 2019-04-08, 13:35   #374
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

23×181 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A suggestion for factordb. enzocreti FactorDB 10 2021-01-05 19:49
Extending Factordb carpetpool FactorDB 6 2017-01-23 11:04
FactorDB PRP's smh FactorDB 231 2015-07-28 02:30
bugged sequence in factordb firejuggler Aliquot Sequences 2 2010-06-15 14:03
FactorDB question Raman Factoring 15 2010-01-28 10:24

All times are UTC. The time now is 15:18.

Mon Jan 18 15:18:33 UTC 2021 up 46 days, 11:29, 0 users, load averages: 1.87, 2.23, 2.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.