NFS question

[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),

(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?

[R.D. Silverman]

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.

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"

[R.D. Silverman]

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
Harvey Cohn's "Advanced Number Theory". It is published by Dover, so
it is really cheap.

[paul0]

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)