Talk:Shanks's square forms factorization

Expert attention needed

This algorithm is somewhat vague and seems incomplete. Furthermore, it does not seem very efficient (or perhaps I did not implement it very well; my implementation took substantially longer than a brute force simple factorization).

I could not check the external link to verify the correctness of this article. This merits review. -- Aprogressivist 19/06/2006

I think that the P's and Q's are not the same variables in the two stages of the solver. BTW, I see identifiers like a, b, n, and so on reused to mean different things wihtin the same article a lot in math articles - maybe I should make that a sub-project of Mathematics. Walt 02:17, 23 June 2006 (UTC)

Added a bit of an introduction and a couple of references. Not had time to look closely at the algorithm given - may find time in a day or two. The article is still in need of considerable work. Madmath789 07:50, 26 June 2006 (UTC)

As described, the method does not seem to work for N = 2^32+1. i get P0 = 65536, Q0 = 1 and Q1 = 1 (in both loops) yielding Pn=65536 and therefore a factor of 1. however 641|2^32+1 —Preceding unsigned comment added by 87.194.130.215 (talk) 15:17, 3 August 2009 (UTC)

I agree with N°1, I did not manage to implement it. On the first try it only factorized a couple of numbers, and on all subsequent attempts, it just failed with an arithmetic exception. Maybe the step-by-step algorithm section ought to be better documented, and a pseudocode would be helpful. I'm having a hard time implementing it ... and there is not many information on the internet about SQUFOF. 118.92.134.217 (talk) 10:31, 2 February 2010 (UTC)

I have updated the algorithm by adding a multiplier. It should be possible to factorise N = 2^32+1 by using the multiplier k = 3. CFB (talk) 11:35, 3 February 2010 (UTC)

I like the algorithm description because it is short, but my implementation does not work for all N. It's ok that for some N the algorithm returns without a result indicating that another k should be tried. However, I get an infinite loop in the second step for N=34, 178, 194, 205, 221, 305, 377, 386, ... That's not so nice ;) 84.134.101.118 (talk) 14:03, 17 January 2015 (UTC)

Ok, I fixed my problem, now the program terminates for all N, I expect. The problem was that it should read "until Q_i is a perfect square at some even i". 84.134.101.118 (talk) 14:57, 17 January 2015 (UTC)

I fixed that point in the article. 84.134.101.118 (talk) 15:43, 17 January 2015 (UTC)

-isation v. -ization

This article has a mixture of both spellings, and ought to be made uniform. The title has 'z' but one of the references has 's' - has anyone any ideas which we should settle for? Madmath789 18:01, 30 August 2006 (UTC)

Fix needed

In the middle of the algorithm is

until $Q_{i}$ is a perfect square at some even $i$.

Initialize $b_{0}=\left\lfloor {\frac {\lfloor {\sqrt {kN}}\rfloor -P_{i-1}}{\sqrt {Q_{i}}}}\right\rfloor ,P_{0}=b_{0}{\sqrt {Q_{i}}}+P_{i-1}$

In the calculation of $b_{0}$ and $P_{0}$ it refers to $P_{i-1}$. The $P_{i-1}$ actually refers to the last value of P calculated in the previous section. Can someone fix this? Bubba73 ^{You talkin' to me?} 03:38, 19 September 2015 (UTC)

Implementations

Hi, I wanted to add a link to my new PSIQS Java package, which contains a SquFoF implementation based on this article. It also realizes two new propositions: 1. Smooth even multipliers work better, 2. The stopping criterion should be ~1.5 * N^(1/5) instead of 4*sqrt(2)*N^(1/4) as proposed by Gower&Wagstaff. Thus I think it would be quite appropriate to have a link to it here. But Wikipedia won't let me because I already linked to my package on the english & german QS pages. ;) If anybody wants to do it, the link is PSIQS If not, I may try another day... Cheers, Till 93.193.186.99 (talk) 14:31, 15 January 2016 (UTC)

Ok, I added the page. I hope that's ok. Till 93.193.170.60 (talk) 17:59, 19 January 2016 (UTC)

A little problem

The difference of two consecutive squares is an odd number, this includes primes. So, 3 = 2² - 1², 5 = 3² - 2², 7 = 4² - 3². — Preceding unsigned comment added by 177.223.210.66 (talk) 18:52, 8 July 2019 (UTC)