Register FAQ Search Today's Posts Mark Forums Read

 2006-07-26, 15:25 #1 jasonp 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 nfs-hacks, 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 2006-07-26 at 15:26
 2006-07-26, 15:40 #2 Chris Card     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
2006-07-26, 16:10   #3
jasonp
Tribal Bullet

Oct 2004

2·13·137 Posts

Quote:
 Originally Posted by Chris Card 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.
The dataset is at home; I'll post more tonight.

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

2006-07-26, 16:49   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165308 Posts

Quote:
 Originally Posted by jasonp 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? 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?
It sounds like a bug. Primes that do not divide any of the norms should be good.

2006-07-27, 03:56   #5
jasonp
Tribal Bullet

Oct 2004

2×13×137 Posts

Quote:
 Originally Posted by R.D. Silverman It sounds like a bug. Primes that do not divide any of the norms should be good.
Okay, I did some poking around and at first glance this looks legitimate.

while factoring
Code:
8377779189172123489970985855514947997654637424323089732438822102729555816483424830899459146547148229 (100 digits)
with rational poly:
R0: -132717012940697753
R1: 1

and algebraic poly:
A0: -63733930540632
A1: 898531118194875
A2: 2326345441429206
A3: 506547343799716
A4: 914690957776800

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 2006-07-27 at 04:11

2006-07-27, 11:47   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×313 Posts

Quote:
 Originally Posted by jasonp Okay, I did some poking around and at first glance this looks legitimate. while factoring Code: 8377779189172123489970985855514947997654637424323089732438822102729555816483424830899459146547148229 (100 digits) with rational poly: 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

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.

2006-07-27, 12:35   #7
jasonp
Tribal Bullet

Oct 2004

2×13×137 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
The siever found (a,b) as listed above (a is negative), and the factorization of the algebraic norm is correct.

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 (a-br) mod p for quadratic characters in this dataset, and GGNFS uses a-br

jasonp

Last fiddled with by jasonp on 2006-07-27 at 12:58

2006-07-27, 14:00   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·3·313 Posts

Quote:
 Originally Posted by jasonp The siever found (a,b) as listed above (a is negative), and the factorization of the algebraic norm is correct. 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 (a-br) mod p for quadratic characters in this dataset, and GGNFS uses a-br jasonp
Yep. My siever computes norms as a + bM, whereas the CWI code
suite uses a - bM. So I flip the sign on output.

 2006-08-05, 21:06 #9 jasonp Tribal Bullet     Oct 2004 67528 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

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2018-03-13 13:37 Ilya Gazman Factoring 3 2016-02-22 11:32 zippy Math 6 2015-07-20 13:09 alpertron Miscellaneous Math 17 2012-04-30 15:28 Romulas Math 3 2010-05-09 03:27

All times are UTC. The time now is 11:30.

Thu Mar 30 11:30:46 UTC 2023 up 224 days, 8:59, 0 users, load averages: 0.84, 0.81, 0.76