20060726, 15:25  #1 
Tribal Bullet
Oct 2004
2·13·137 Posts 
NFS and quadratic characters
Quick question on the use of quadratic characters in the linear algebra phase of NFS; actually I'm seeing weird behavior in my implementation and am wondering if this is a bug.
According to references, for algebraic polynomial f(x) and a set S of relations, a prime p can be used for quadratic characters if for each root r of f(x) mod p we assure than (a+br) mod p is never zero, where a and b are the coordinates of each relation in S. The linear algebra phase of msieve's GNFS implementation chooses the primes to use for quadratic characters starting with the first prime larger than any that appear in relations. Should this be enough to assure (a+br) mod p is never zero? I take this condition to mean that p would never divide the norm of a relation, which should be guaranteed if p is chosen this way. The problem is that out of 610,000 relations in my test factorization, and 32 (p,r) pairs used for quadratic characters, there are two cases where (a+br) mod p = 0. Does this indicate a bug? Is this supposed to be possible, and can it spoil the linear algebra if it's just ignored? Thanks, jasonp PS: I originally tried posting this to nfshacks, but apparently my ISP rejects enough mail from yahoo that they're retaliating by bouncing my mail to them. Last fiddled with by jasonp on 20060726 at 15:26 
20060726, 15:40  #2 
Aug 2004
7·19 Posts 
That does sound odd.
Can you show us the 2 examples which had (a + br) = 0 mod p? However, if you've got enough quadratic characters that don't behave like this, I think you should be ok, because of the way quadratic characters work to make a square more probable. Chris 
20060726, 16:10  #3  
Tribal Bullet
Oct 2004
2·13·137 Posts 
Quote:
Assuming this isn't a bug, does a zero remainder just mean that that particular p doesn't provide any information about that particular (a,b)? jasonp 

20060726, 16:49  #4  
"Bob Silverman"
Nov 2003
North of Boston
16530_{8} Posts 
Quote:


20060727, 03:56  #5  
Tribal Bullet
Oct 2004
2×13×137 Posts 
Quote:
while factoring Code:
8377779189172123489970985855514947997654637424323089732438822102729555816483424830899459146547148229 (100 digits) R0: 132717012940697753 R1: 1 and algebraic poly: A0: 63733930540632 A1: 898531118194875 A2: 2326345441429206 A3: 506547343799716 A4: 914690957776800 A5: 203467906800000 < leading coefficient relation: a = 1130965, b = 838792 has algebraic factors E75,20FB,2D89,3079,7207,667D9,79D,161,B,D,6B,13,2,2,2,2,2,2,2,111B1B for the quadratic character, p = 67108463 which has root r = 27059739, and sure enough (a + b * r) mod p = 0 Update: using a = +1130965 the relation would have a factor of p, so I may have the root negated jasonp Last fiddled with by jasonp on 20060727 at 04:11 

20060727, 11:47  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×313 Posts 
Quote:
Did the siever actually find this relation, but fail to find the factor 67108463? Did the siever miss the relation? If the siever found the relation and included it among the outputs , then the prime should not have been selected for a quadratic character. If the siever missed the relation, it is still OK to use the prime. Something doesn't seem right. 

20060727, 12:35  #7  
Tribal Bullet
Oct 2004
2×13×137 Posts 
Quote:
The factorization of the algebraic norm of (a,b) contains p=67108463, and for this prime the computed root r is such that (a+br) mod p is zero. I think the problem is that I should be using r to compute quadratic characters. Some references use algebraic ideals of the form a + b \alpha, others use a  b \alpha, and my choice of roots may be using the wrong convention. I just checked: there are no zero values of (abr) mod p for quadratic characters in this dataset, and GGNFS uses abr jasonp Last fiddled with by jasonp on 20060727 at 12:58 

20060727, 14:00  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·313 Posts 
Quote:
suite uses a  bM. So I flip the sign on output. 

20060805, 21:06  #9 
Tribal Bullet
Oct 2004
6752_{8} Posts 
how many QCB entries?
While we're on the subject of quadratic characters, if every extra entry in the quadratic character base reduces by half the odds that the result of the linear algebra is not a square, why do references insist on a great many entries? The ggnfs source uses 62 of them and earlier comments used to state that that many 'should be enough'. Why not just 32? Is it because the odds of a false positive go up as the number of relations increase?
jasonp 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quadratic PRP test  carpetpool  Miscellaneous Math  5  20180313 13:37 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
quadratic residues  zippy  Math  6  20150720 13:09 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
Quadratic Residues  Romulas  Math  3  20100509 03:27 