20120510, 09:24  #1 
Sep 2011
3·19 Posts 
NFS question
I'm reading Michael Case's paper on NFS.
Does the pair found by sieving need to be smooth: (1) separately on the three factor bases (rational, algebraic and quadratic character base), (2) on any of the bases, or (3) on all of the bases combined? Also, I don't understand the purpose of the quadratic character base. Why can't it just be a part of the algebraic factor base? 
20120510, 09:58  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
base. Quote:
Wikipedia?? A character is a multiplicative function, defined on a group (i.e. its domain is a group) and whose range is a root of unity. For NFS, we use quadratic residues of ideals that appear in a relation modulo a set of primes not in the factor base. Being a square in Q[alpha] is not sufficient to guarantee that an element of Q[alpha] will be a square when lifted to Q because Q[alpha] is almost surely not a UFD. Now, an integer (rational integer) is a square when it is a square modulo sufficiently many primes. Thus, we take the ideals in a relation and compute whether they are a square modulo a set of primes that are external to the factor base. These are the quadratic characters. Now, after the LA, since we have forced the final product to be a square modulo sufficiently many primes, we also force it to be a square in Q. We need to figure out which set of relations, which when multiplied, will yield a square in Q and not just a square in Q[alpha]. Understanding all of this requires some background in number theory/group theory. Thr characters are not part of the "factor base" 

20120510, 11:09  #3  
Nov 2003
1110100100100_{2} Posts 
Quote:
Harvey Cohn's "Advanced Number Theory". It is published by Dover, so it is really cheap. Last fiddled with by R.D. Silverman on 20120510 at 11:09 Reason: typo 

20120511, 13:34  #4 
Sep 2011
3·19 Posts 
Thank you for the replies. After rereading Briggs paper on NFS (it complements Case's quite well), I understand now that the characters are not part of the factor base. The value on the matrix corresponding to the characters is dependent on the results of the Legendre symbol. (i.e. (a+bs)/q)
