2015-01-01, 18:16 | #1 |
Sep 2011
71_{8} 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 |
Dec 2012
The Netherlands
3×499 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 |
Tribal Bullet
Oct 2004
3×1,163 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. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Sums of all Squares | davar55 | Puzzles | 183 | 2019-12-12 22:31 |
Regarding Squares | a1call | Miscellaneous Math | 42 | 2017-02-03 01:29 |
A Sum of Squares Problem | MattcAnderson | Puzzles | 7 | 2014-08-17 07:20 |
squares or not squares | m_f_h | Puzzles | 45 | 2007-06-15 17:46 |
Identifing perfect squares and calculating square roots.. | dsouza123 | Math | 2 | 2003-07-19 17:17 |