Fixing the large dataset bug - Page 2

fivemack · 2014-06-23, 14:46

What do you mean by 'the second term in the GCD is zero'? x^112-1 evaluates to zero mod 113 for all values of x, but that doesn't make the polynomial identically zero!

And in any case the GCD of f and the zero polynomial would be f.

Code:

? g=(x^7-1)/(x-1)
%14 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
? gcd(g,Mod(1,113)*x^112-Mod(1,113))
%15 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

which I take as meaning that g has six roots and they're not repeated

R.D. Silverman · 2014-06-23, 16:39

Quote:

Originally Posted by fivemack

What do you mean by 'the second term in the GCD is zero'? x^112-1 evaluates to zero mod 113 for all values of x,

???? Try x = 0

jasonp · 2014-06-24, 13:55

Ouch, I forgot that GCD(n, 0) is n, so the fix I mentioned was actually wrong.

There was also another problem in Msieve's finite field rootfinder; the code computes g(x) = gcd(f(x), x^p-1) to get the product of the linear polynomial roots of f(x) = 0 mod p. If g(x) has degree > 0, the code then tries to pick a constant c so that

gcd(g(x), (x-c)^((p-1)/2) - 1)

is not 1 or g(x). If such a c is found, the algorithm recurses. The loop that tries each c in increasing order was not rejecting a gcd of f(x).

Each c is supposed to have a 50% chance of splitting g(x), but the really strange thing is that chris2be8's 107-digit example has a p for which thousands of different c do *not* split g(x). I don't have the dataset with me now but the offending value of p is around 10 million. About 1 in 10000 choices of c yield a gcd of g(x), the rest yield a gcd of 1.

Am I going to have to dig into the rootfinder's exponentiation code because there's an arithmetic mistake somewhere, or is this behavior actually legitimate?

It's really depressing how many bugs and corner cases the rootfinder has had, but I thought for years that I had fixed them all.

fivemack · 2014-06-24, 15:20

I'd be interested to know the value of p, but I'd expect this to be a bug rather than a weird mathematical situation; what you're saying is that the six roots are such that r+C are either all quadratic residues or all not for all C, and I'd be astounded if quadratic residues modulo a large prime were that far from being randomly distributed.

CRGreathouse · 2014-06-24, 15:37

Unrelated: I haven't searched through enough of the source to be certain, but shouldn't line 776 have

Code:

if ((parity&1) == 0)

rather than

Code:

if (parity == 0)

?

chris2be8 · 2014-06-24, 15:59

The poly is:

Code:

factordb: (492200791^17-1)/898756619763091557308035931484430830
# Record 914 match 297 from random_composites.txt
# SNFS difficulty is 147., GNFS equivalent is 105, GNFS difficulty is 112, degree 4
n: 6497961323461307991128472650033413888394925930169998950345348795918901386491783630546569495523896984880604880941
# 492200791^17-1^17, difficulty: 147.77, skewness: 0.01, alpha: 0.00
# cost: 9.75535e+14, est. time: 0.46 GHz days (not accurate yet!)
skew: 0.007
c4: 492200791
c0: -1
Y1: -1
Y0: 58690691876260226474178666941513761
m: 58690691876260226474178666941513761
type: snfs

The first line is the factordb entry I'm trying to factor, most of the rest was generated by phi.

I've seen a few other cases where msieve failed, I could probably find them if you want.

Chris

R.D. Silverman · 2014-06-24, 16:17

Quote:

Originally Posted by fivemack

I'd be interested to know the value of p, but I'd expect this to be a bug rather than a weird mathematical situation; what you're saying is that the six roots are such that r+C are either all quadratic residues or all not for all C, and I'd be astounded if quadratic residues modulo a large prime were that far from being randomly distributed.

They are not. And RH places a limit on how many successive qr's can
exist. It is something like O(log^2 p)

chris2be8 · 2014-06-24, 20:22

I've found two more polys that caused the square root stage to crash. But I don't have the relations for them any more so can't re-run filtering.

Code:

factordb: (8^118+2^118-1)/11485278757
# Record 40 from snfsall.txt
# SNFS difficulty is 108, GNFS equivalent is 77, GNFS difficulty is 97, degree 6
n: 3195044598588939950251582241577925599907582619824479196121388612996532283445626419056645024163411
type: snfs
name: d2_354_118_-1
# m=2^59
m: 576460752303423488
c6: 1
c2: 1
c0: -1
lss: 0


factordb: (696403^23-1)/78587209790500632102
# Record 208 from snfs.txt
# Base 696403 is prime
# Exponent 23 is prime
# 696403^23-1 = 78587209790500632102 * 3093447122765350829978426140979773179755047840171555213678553642175625380833547265391459017312799174 498299762255663
# SNFS diff = 152  SNFS equiv = 109  GNFS diff = 115 Degree = 5
n: 3093447122765350829978426140979773179755047840171555213678553642175625380833547265391459017312799174498299762255663
type: snfs
name: f696403_23-1
# m = 696403^5
m:  163795952784836201847941242243
c5: 1
c4: 0
c3: 0
c2: 0
c1: 0
c0: -484977138409

Also the following appeared in /var/log/messages when the last msieve run failed:
Jun 24 18:43:58 laptop kernel: msieve[3460]: segfault at 00007ffff2fffd48 rip 000000391fc2ae12 rsp 00007ffff2fffd50 error 6

Chris

jasonp · 2014-06-25, 01:25

p is 10743097, and when Pari failed to solve for the roots I realized p is composite, so this will never work. So it's a problem with the siever! The
offending relation is

Code:

368,487:42637,1d3a61:a3ed39,49f8d
                     ^^^^^

There is no primality test of factors that appear in relations; do we need one?

CRGreathouse · 2014-06-25, 02:53

Quote:

Originally Posted by jasonp

There is no primality test of factors that appear in relations; do we need one?

I don't know -- but if you come across this sort of error maybe you could just back up and handle composite factors? From an efficiency standpoint that might be better.

jasonp · 2014-06-25, 11:43

The error is a crash, infinite loop and possibly niether of these but an unusable matrix. I'd rather check primality ahead of time :)

2014-06-23, 14:46	#12
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	What do you mean by 'the second term in the GCD is zero'? x^112-1 evaluates to zero mod 113 for all values of x, but that doesn't make the polynomial identically zero! And in any case the GCD of f and the zero polynomial would be f. Code: ? g=(x^7-1)/(x-1) %14 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 ? gcd(g,Mod(1,113)*x^112-Mod(1,113)) %15 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 which I take as meaning that g has six roots and they're not repeated

2014-06-24, 13:55	#14
jasonp Tribal Bullet Oct 2004 3,541 Posts	Ouch, I forgot that GCD(n, 0) is n, so the fix I mentioned was actually wrong. There was also another problem in Msieve's finite field rootfinder; the code computes g(x) = gcd(f(x), x^p-1) to get the product of the linear polynomial roots of f(x) = 0 mod p. If g(x) has degree > 0, the code then tries to pick a constant c so that gcd(g(x), (x-c)^((p-1)/2) - 1) is not 1 or g(x). If such a c is found, the algorithm recurses. The loop that tries each c in increasing order was not rejecting a gcd of f(x). Each c is supposed to have a 50% chance of splitting g(x), but the really strange thing is that chris2be8's 107-digit example has a p for which thousands of different c do not split g(x). I don't have the dataset with me now but the offending value of p is around 10 million. About 1 in 10000 choices of c yield a gcd of g(x), the rest yield a gcd of 1. Am I going to have to dig into the rootfinder's exponentiation code because there's an arithmetic mistake somewhere, or is this behavior actually legitimate? It's really depressing how many bugs and corner cases the rootfinder has had, but I thought for years that I had fixed them all. Last fiddled with by jasonp on 2014-06-24 at 13:58 Reason: parentheses

2014-06-24, 15:37	#16
CRGreathouse Aug 2006 1011101011011₂ Posts	Unrelated: I haven't searched through enough of the source to be certain, but shouldn't line 776 have Code: if ((parity&1) == 0) rather than Code: if (parity == 0) ?

2014-06-25, 01:25	#20
jasonp Tribal Bullet Oct 2004 6725₈ Posts	p is 10743097, and when Pari failed to solve for the roots I realized p is composite, so this will never work. So it's a problem with the siever! The offending relation is Code: 368,487:42637,1d3a61:a3ed39,49f8d ^^^^^ There is no primality test of factors that appear in relations; do we need one?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
48-bit large primes!	jasonp	Msieve	24	2010-06-01 19:14
a^n mod m (with large n)	Romulas	Math	3	2010-05-08 20:11
NFS with 5 and 6 large primes	jasonp	Factoring	4	2007-12-04 18:32
Why only three large primes	fivemack	Factoring	18	2007-05-10 12:14
very large exponents	pacionet	Data	4	2005-11-04 20:10

2014-06-24, 15:20	#15
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6419₁₀ Posts	I'd be interested to know the value of p, but I'd expect this to be a bug rather than a weird mathematical situation; what you're saying is that the six roots are such that r+C are either all quadratic residues or all not for all C, and I'd be astounded if quadratic residues modulo a large prime were that far from being randomly distributed.

2014-06-25, 11:43	#22
jasonp Tribal Bullet Oct 2004 3,541 Posts	The error is a crash, infinite loop and possibly niether of these but an unusable matrix. I'd rather check primality ahead of time :)