Ring Square Roots in NFS

paul0 · 2014-10-11, 07:52

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?

R.D. Silverman · 2014-10-11, 08:07

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

axn · 2014-10-11, 10:55

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).

jasonp · 2014-10-11, 14:32

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.

paul0 · 2015-01-09, 14:57

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.

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?

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

2014-10-11, 14:32	#4
jasonp Tribal Bullet Oct 2004 6725₈ 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.