Shanks's square forms factorization: Difference between revisions

Revision as of 20:42, 30 October 2023

Revision as of 18:03, 31 October 2023

Line 42:

Then if <math>f=\gcd(N,P_i)</math> is not equal to <math>1</math> and not equal to <math>N</math>, then <math>f</math> is a non-trivial factor of <math>N</math>. Otherwise try another value of <math>k</math>.{{cn|date=October 2023}}

Shanks's method has time complexity <math>O(\sqrt[4]{N})</math>.<ref>{{Harvcol|Riesel, 1994, |194|p. =189}}</ref>

<ref>{{Harvcol|Soltis|2004|pp=10–12}}</ref>

Stephen S. McMath wrote