Fixing the large dataset bug

[jasonp]

Several of you have huge datasets lying around, for which the filtering in Msieve produces unusable matrices or even flat out crashes.

Thanks to an observation of RichD, can anyone with such a large dataset (more that about 750M relations) change the following structure at line 133 of include/common.h

typedef struct {
  uint32 blob_words;
  uint32 hash_words;
  uint32 *hashtable;
  uint32 log2_hashtable_size;
  uint32 num_used;
  uint32 congestion_target;
  uint32 *match_array;
  uint32 match_array_size;
  uint32 match_array_alloc;
} hashtable_t;

to

typedef struct {
  uint32 blob_words;
  uint32 hash_words;
  uint32 *hashtable;
  uint32 log2_hashtable_size;
  size_t num_used;
  size_t congestion_target;
  uint32 *match_array;
  size_t match_array_size;
  size_t match_array_alloc;
} hashtable_t;

and retry the filtering? I think in the case of singleton removal this will avoid an overflow out of 4GB when the number of ideals exceeds about 2^28.

[jasonp]

Actually, upon further review it is unlikely the above will fix anything; what I thought was an arrays size is actually a count of array elements, which has a harder time exceeding 2^32.

[jasonp]

Thanks to chris2be8, I've committed SVN 966 to detect an edge case deep in the finite field rootfinder; without that fix, certain SNFS polynomials would generate invalid free relations that could conceivably cause crashes during singleton removal. This might be a fix for the large dataset bug.

For my edification, is it really true that there are *no* primes p such that x^6+x^5+x^4+x^3+x^2+x+1=0 mod p has 6 linear roots? The fix would imply this is the case, which further implies there are SNFS problems that cannot generate any free relations, which I thought was impossible.

[henryzz]

I suppose someone needs to remove all the free relations from a crashing job and run the filtering again.

[fivemack]

Originally Posted by jasonp

Thanks to chris2be8, I've committed SVN 966 to detect an edge case deep in the finite field rootfinder; without that fix, certain SNFS polynomials would generate invalid free relations that could conceivably cause crashes during singleton removal. This might be a fix for the large dataset bug.

For my edification, is it really true that there are *no* primes p such that x^6+x^5+x^4+x^3+x^2+x+1=0 mod p has 6 linear roots? The fix would imply this is the case, which further implies there are SNFS problems that cannot generate any free relations, which I thought was impossible.

If p==1 mod 7, and t is a primitive root mod p, then (t^6)^j is a root of that polynomial for all j; am I missing something?

The polynomial is (x^7-1)/(x-1); if p is not equal to 1 mod 7, then it will have no roots (because a root would be an element of the group of order 7, and 7 does not divide the order of the group!)

[R.D. Silverman]

Originally Posted by jasonp

For my edification, is it really true that there are *no* primes p such that x^6+x^5+x^4+x^3+x^2+x+1=0 mod p has 6 linear roots? The fix would imply this is the case, which further implies there are SNFS problems that cannot generate any free relations, which I thought was impossible.

The Galois group is CYCLIC!!!!!!! (generated by a primitive 7th
root of unity)........

Further hint: consider primes that are 1 mod 7.......

[R.D. Silverman]

Originally Posted by R.D. Silverman

The Galois group is CYCLIC!!!!!!! (generated by a primitive 7th
root of unity)........

Further hint: consider primes that are 1 mod 7.......

Further hint: Chebotarev Density Thm.

Consider: What is the order of closure for the Galois group?

[jasonp]

This failing example has 107 digits; all the primes in the factor base are 1 mod 7. If f(x) = x^6+x^5+x^4+x^3+x^2+x+1, the finite field rootfinder first computes gcd(f(x), x^(p-1)-1) to determine the product of all the linear polynomial roots of f(x) = 0 mod p. However, the second term in the above is always 0, so this test concludes that no p is a root of f(x) = 0 mod p. Without the fix mentioned previously, the gcd would also crash.

That obviously isn't right, since the p chosen for free relations always shadow a p that appers in ordinary relations. So does the rootfinder need a special case to work correctly for polynomials like this f(x)?

[R.D. Silverman]

Originally Posted by jasonp

This failing example has 107 digits; all the primes in the factor base are 1 mod 7. If f(x) = x^6+x^5+x^4+x^3+x^2+x+1, the finite field rootfinder first computes gcd(f(x), x^(p-1)-1) to determine the product of all the linear polynomial roots of f(x) = 0 mod p. However, the second term in the above is always 0, so this test concludes that no p is a root of f(x) = 0 mod p. Without the fix mentioned previously, the gcd would also crash.

That obviously isn't right, since the p chosen for free relations always shadow a p that appers in ordinary relations. So does the rootfinder need a special case to work correctly for polynomials like this f(x)?

'the rootfinder' or 'a rootfinder'???

I can't speak for the first case, since I do not know what the code does,
but the answer for the second case is no. My code has no special cases.

[CRGreathouse]

Originally Posted by fivemack

If p==1 mod 7, and t is a primitive root mod p, then (t^6)^j is a root of that polynomial for all j; am I missing something?

Let p = 29, t = 2, and j = 1. Then p = 1 mod 7 and t is a primitive root mod p but (t^6)^j = 64 = 6 mod 29 is not a root of x^6+x^5+x^4+x^3+x^2+x+1 mod p. Am *I* missing something?

The factorization I see is (x + 4)(x + 5)(x + 6)(x + 9)(x + 13)(x + 22) = (x - 7)(x - 16)(x - 20)(x - 23)(x - 24)(x - 25) mod 29.

[jasonp]

The rootfinder in the Msieve code, starting on line 703 of here.

Consider p=113. Both wolfram alpha and the code above compute that gcd(f(x), x^112-1) is 1 because the second term in the GCD is zero. But this is supposed to be a polynomial that is a product of all the linear roots of f(x)=0 mod 113. Yet f(x) = 0 mod 113 has roots 16, 28, 30, 49, 106 and 109.