A simple explanation of NFS?

paul0 · 2011-11-02, 14:19

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?

jasonp · 2011-11-02, 14:28

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

LaurV · 2011-11-02, 15:38

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)

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

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.

LaurV · 2011-11-02, 15:54

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".

paul0 · 2011-11-02, 23:21

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.

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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
FFT explanation for non math guys	creative1	Math	61	2019-04-05 16:39
Laymans explanation of RSA encryption	Fusion_power	Programming	3	2013-11-04 20:50
Explanation for simpleton please.	Flatlander	Science & Technology	15	2011-08-06 13:32
Bounds explanation	Uncwilly	Lounge	4	2011-04-01 19:15
explanation on polynomial	firejuggler	Aliquot Sequences	7	2010-05-29 02:46

2011-11-02, 14:28	#2
jasonp Tribal Bullet Oct 2004 DCE₁₆ 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:54	#5
LaurV Romulan Interpreter Jun 2011 Thailand 2³·19·61 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".