Ring Square Roots in NFS
 

I'm reading Briggs' ( [url]https://www.math.vt.edu/people/ezbrown/doc/briggs_gnfs_thesis.pdf[/url] ) 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?

[QUOTE=paul0;384963]I'm reading Briggs' ( [url]https://www.math.vt.edu/people/ezbrown/doc/briggs_gnfs_thesis.pdf[/url] ) 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?

[/QUOTE]

Even if one assumes that the ring is a UFD, your question can be answered
in one word: units

[QUOTE=paul0;384963]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?[/QUOTE]

(mod 45113), not (mod 45331).

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.

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.