mersenneforum.org Ring Square Roots in NFS
 Register FAQ Search Today's Posts Mark Forums Read

 2014-10-11, 07:52 #1 paul0   Sep 2011 3×19 Posts Ring Square Roots in NFS I'm reading Briggs' ( https://www.math.vt.edu/people/ezbro...nfs_thesis.pdf ) paper on NFS. Although the paper states that this calculation is not done explicitly, I still want to know why It can't be done this way. In section 5.8, it lists smooth (a,b) pairs: (-1+θ),(3+θ)... whose product creates a square in Z[θ]. My question is, why can't we calculate the product this way: (-1+31)*(3+31)... to produce a square? Why does the homomorphism prohibit this? I just noticed something, at the end of section 5.8, it says x = 43922 = ... = 694683807559 (mod 45331) which I don't think is true. Am I missing something here?
2014-10-11, 08:07   #2
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by paul0 I'm reading Briggs' ( https://www.math.vt.edu/people/ezbro...nfs_thesis.pdf ) paper on NFS. Although the paper states that this calculation is not done explicitly, I still want to know why It can't be done this way. In section 5.8, it lists smooth (a,b) pairs: (-1+θ),(3+θ)... whose product creates a square in Z[θ]. My question is, why can't we calculate the product this way: (-1+31)*(3+31)... to produce a square? Why does the homomorphism prohibit this?
Even if one assumes that the ring is a UFD, your question can be answered
in one word: units

2014-10-11, 10:55   #3
axn

Jun 2003

10010101010012 Posts

Quote:
 Originally Posted by paul0 I just noticed something, at the end of section 5.8, it says x = 43922 = ... = 694683807559 (mod 45331) which I don't think is true. Am I missing something here?
(mod 45113), not (mod 45331).

 2014-10-11, 14:32 #4 jasonp Tribal Bullet     Oct 2004 3×1,163 Posts To expand on what Bob said, if you knew a set of units in the number field then an NFS square root would look like a QS square root and would be easy. Just decompose each relation into the set of units, sum them, and then 'cut each in half'. Unfortunately in a general number field it is infeasible to calculate a set of units. Early SNFS factorizations did have this special structure, and the square root would have been intractable on computers of that time if they did not. In general it's even worse than that, because a number field has to be a little bit special for square roots to be unique; NFS has to assume that square roots are not unique, and take special measures (i.e. quadratic characters) to calculate a field element that will work correctly as an algebraic square root.
 2015-01-09, 14:57 #5 paul0   Sep 2011 3×19 Posts I figured out the answer to my own question: The homomorphism only guarantees a congruence modulo n, so multiplying the smooths directly will give you a congruence, but not a square.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2018-01-05 09:30 Flatlander Lounge 19 2013-09-24 05:27 Raman Math 4 2012-02-20 07:30 JohnFullspeed Programming 7 2011-05-27 07:09 dsouza123 Math 2 2003-07-19 17:17

All times are UTC. The time now is 23:25.

Wed Nov 25 23:25:40 UTC 2020 up 76 days, 20:36, 3 users, load averages: 1.14, 1.30, 1.31