Talk:Shanks's square forms factorization

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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 ;) In the mentioned McMath article, it is said that in the second step there are two iterations that have to be carried out in parallel. Maybe the problem here is that one of those is missing? 84.134.101.118 (talk) 14:03, 17 January 2015 (UTC)[reply]

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)[reply]

-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)[reply]