Go Back > Math Stuff > Computer Science & Computational Number Theory

Thread Tools
Old 2015-01-01, 18:16   #1
Sep 2011

3×19 Posts
Default 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.
paul0 is offline   Reply With Quote
Old 2015-01-02, 10:00   #2
Nick's Avatar
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.
Nick is offline   Reply With Quote
Old 2015-01-02, 14:21   #3
Tribal Bullet
jasonp's Avatar
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.
jasonp is offline   Reply With Quote

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

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

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