mersenneforum.org A simple explanation of NFS?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-02, 14:19 #1 paul0   Sep 2011 3·19 Posts A simple explanation of NFS? I fully understand the Quadratic Sieve. As far as I know right now, NFS uses a different number system that is dependent on the polynomial used. The factor base is also dependent on this polynomial. Please don't include optimizations so that the explanation would be simple. (for example, using trial division instead of the lattice sieve) If an explanation this simple isn't possible, what topics should I read more about?
 2011-11-02, 14:28 #2 jasonp Tribal Bullet     Oct 2004 33·131 Posts See the section 'Number Field Sieve References' near the bottom of this for what I think is a complete list of the introductory papers on NFS. Your understanding is correct; the algebraic NFS polynomial describes a number field, and the way that polynomial is constructed allows for a 'trap door' that converts elements of the number field back to integers modulo the number N to be factored. Thus a square root in the number field (hopefully) becomes a square root modulo N, which lets the congruence-of-squares method work. The complications arise because number fields can do all sorts of weird things that prevent finding - a square root - easily - that is unique - and corresponds to the square in the number field
2011-11-02, 15:38   #3
LaurV
Romulan Interpreter

Jun 2011
Thailand

5×1,877 Posts

Quote:
 Originally Posted by jasonp - and corresponds to the square in the number field
(or corresponds to a square root mod N? not clear for me here)

2011-11-02, 15:44   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV (or corresponds to a square root mod N? not clear for me here)
Square in the field is correct. It corresponds to a square mod N because
of the ring homomorphism that maps a complex root of the polynomial to
a root of the polynomial in Z/NZ.

 2011-11-02, 15:54 #5 LaurV Romulan Interpreter     Jun 2011 Thailand 5×1,877 Posts That is somehow close to my borderline of understanding, but I trust you. I am exactly in the situation of OP paul0: perfectly understanding QS with all its variations, even did some personal implementations for small numbers (default C types) to understand what's going on, but when it comes to number fields, I am totally "tabula rasa".
2011-11-02, 23:21   #6
paul0

Sep 2011

3·19 Posts

Quote:
 Originally Posted by LaurV That is somehow close to my borderline of understanding, but I trust you. I am exactly in the situation of OP paul0: perfectly understanding QS with all its variations, even did some personal implementations for small numbers (default C types) to understand what's going on, but when it comes to number fields, I am totally "tabula rasa".
I actually wrote MPQS in Java using the BigInteger class. Very inefficient, but it works.

Thanks for the replies, my school's library carries the book by Pollard.

Last fiddled with by paul0 on 2011-11-02 at 23:27

 Similar Threads Thread Thread Starter Forum Replies Last Post creative1 Math 61 2019-04-05 16:39 Fusion_power Programming 3 2013-11-04 20:50 Flatlander Science & Technology 15 2011-08-06 13:32 Uncwilly Lounge 4 2011-04-01 19:15 firejuggler Aliquot Sequences 7 2010-05-29 02:46

All times are UTC. The time now is 17:18.

Wed Apr 21 17:18:32 UTC 2021 up 13 days, 11:59, 0 users, load averages: 1.96, 2.18, 2.34