mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-05-10, 09:24   #1
paul0
 
Sep 2011

3·19 Posts
Default 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?
paul0 is offline   Reply With Quote
Old 2012-05-10, 09:58   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by paul0 View Post
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"
R.D. Silverman is offline   Reply With Quote
Old 2012-05-10, 11:09   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.

Last fiddled with by R.D. Silverman on 2012-05-10 at 11:09 Reason: typo
R.D. Silverman is offline   Reply With Quote
Old 2012-05-11, 13:34   #4
paul0
 
Sep 2011

3·19 Posts
Default

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)
paul0 is offline   Reply With Quote
Reply

Thread Tools


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.