mersenneforum.org Perfect squares in NFS
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2015-01-01, 18:16 #1 paul0   Sep 2011 3×19 Posts Perfect squares in NFS My understanding of NFS has really improved, in fact, I've implemented it in Gaussian integers. In general polynomials with f(α)=0, the product generated by sieving and linear algebra is multiplied by f'(α). I don't have a good background on algebraic number theory, but is my line of reasoning correct: The norm and quadratic character tests do not guarantee a square in Z[α], only a square in a "containing ring" O of Z[α] (i.e. Z[α] is a subset of O) is guaranteed. I may not be able to understand it, but please try to explain: why will multiplying the product with f'(α) make a square in Z[α]? I won't be surprised if people who implement NFS don't fully understand it.
 2015-01-02, 10:00 #2 Nick     Dec 2012 The Netherlands 412 Posts The standard reference is the paper "The Number Field Sieve" by Arjen & Hendrik Lenstra, Manasse and Pollard, also published in the book "The development of the Number Field Sieve" edited by the Lenstra brothers (ISBN 9783540570134). It was published in 1993, but progress since then has been mainly technical rather than theoretical, making it still up-to-date. I don't immediately see which step in the algorithm (as presented there) you are referring to, but perhaps someone else does.
 2015-01-02, 14:21 #3 jasonp Tribal Bullet     Oct 2004 2·29·61 Posts My understanding is that OP is correct as to why the derivative of the algebraic poly is involved in the NFS square root phase. See also note 2.4.1 of Briggs' introduction to the number field sieve, which references the paper 'Factoring Integers with the Number Field Sieve' by Buhler, Lenstra and Pomerance, published in the book given by Nick above. This paper is pretty much the only reference that goes step by step through the NFS square root; I wouldn't have been able to implement the algorithm without it.

 Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Puzzles 183 2019-12-12 22:31 a1call Miscellaneous Math 42 2017-02-03 01:29 MattcAnderson Puzzles 7 2014-08-17 07:20 m_f_h Puzzles 45 2007-06-15 17:46 dsouza123 Math 2 2003-07-19 17:17

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

Tue May 18 23:01:40 UTC 2021 up 40 days, 17:42, 0 users, load averages: 3.18, 2.25, 1.89