 mersenneforum.org > Math NFS question
 Register FAQ Search Today's Posts Mark Forums Read 2012-05-10, 09:24 #1 paul0   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?   2012-05-10, 09:58   #2
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by paul0 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),
Do you know what a character is? The characters are not part of the factor
base.

Quote:
 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?
It seems that you do not know what a character is. May I suggest
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"   2012-05-10, 11:09   #3
R.D. Silverman

Nov 2003

11101001001002 Posts Quote:
 Originally Posted by R.D. Silverman Do you know what a character is? The characters are not part of the factor base. It seems that you do not know what a character is. May I suggest 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"
An excellent reference for studying characters can be found in
it is really cheap.

Last fiddled with by R.D. Silverman on 2012-05-10 at 11:09 Reason: typo   2012-05-11, 13:34 #4 paul0   Sep 2011 3·19 Posts Thank you for the replies. After re-reading 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)  Thread Tools Show Printable Version Email this Page

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

Tue Oct 26 22:30:16 UTC 2021 up 95 days, 16:59, 1 user, load averages: 1.45, 1.19, 1.20