20111102, 14:19  #1 
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? 
20111102, 14:28  #2 
Tribal Bullet
Oct 2004
2·29·61 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 congruenceofsquares 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 
20111102, 15:38  #3 
Romulan Interpreter
Jun 2011
Thailand
9447_{10} Posts 

20111102, 15:44  #4 
Nov 2003
2^{2}×5×373 Posts 

20111102, 15:54  #5 
Romulan Interpreter
Jun 2011
Thailand
3×47×67 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". 
20111102, 23:21  #6  
Sep 2011
3×19 Posts 
Quote:
Thanks for the replies, my school's library carries the book by Pollard. Last fiddled with by paul0 on 20111102 at 23:27 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
FFT explanation for non math guys  creative1  Math  61  20190405 16:39 
Laymans explanation of RSA encryption  Fusion_power  Programming  3  20131104 20:50 
Explanation for simpleton please.  Flatlander  Science & Technology  15  20110806 13:32 
Bounds explanation  Uncwilly  Lounge  4  20110401 19:15 
explanation on polynomial  firejuggler  Aliquot Sequences  7  20100529 02:46 