mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-10-11, 07:52   #1
paul0
 
Sep 2011

2×52 Posts
Default 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?
paul0 is offline   Reply With Quote
Old 2014-10-11, 08:07   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25·233 Posts
Default

Quote:
Originally Posted by paul0 View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2014-10-11, 10:55   #3
axn
 
axn's Avatar
 
Jun 2003

41·113 Posts
Default

Quote:
Originally Posted by paul0 View Post
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).
axn is online now   Reply With Quote
Old 2014-10-11, 14:32   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·881 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2015-01-09, 14:57   #5
paul0
 
Sep 2011

1100102 Posts
Default

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.
paul0 is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 18:38.

Sat Jul 11 18:38:45 UTC 2020 up 108 days, 16:11, 0 users, load averages: 1.44, 1.56, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.