mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-11-02, 14:19   #1
paul0
 
Sep 2011

3·19 Posts
Default 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?
paul0 is offline   Reply With Quote
Old 2011-11-02, 14:28   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2011-11-02, 15:38   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×1,877 Posts
Default

Quote:
Originally Posted by jasonp View Post
- and corresponds to the square in the number field
(or corresponds to a square root mod N? not clear for me here)
LaurV is online now   Reply With Quote
Old 2011-11-02, 15:44   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
(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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-02, 15:54   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×1,877 Posts
Default

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".
LaurV is online now   Reply With Quote
Old 2011-11-02, 23:21   #6
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
paul0 is offline   Reply With Quote
Reply

Thread Tools


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

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

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.