20141011, 07:52  #1 
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? 
20141011, 08:07  #2  
Nov 2003
2^{6}×113 Posts 
Quote:
in one word: units 

20141011, 10:55  #3 
Jun 2003
1001010101001_{2} Posts 

20141011, 14:32  #4 
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. 
20150109, 14:57  #5 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Ring of integers in an unknown field  carpetpool  Abstract Algebra & Algebraic Number Theory  1  20180105 09:30 
Identifying ring inscription  Flatlander  Lounge  19  20130924 05:27 
2/3 Powers being viewed over the Ring Z/(10^n)Z  Raman  Math  4  20120220 07:30 
Ring Cardinal?  JohnFullspeed  Programming  7  20110527 07:09 
Identifing perfect squares and calculating square roots..  dsouza123  Math  2  20030719 17:17 