Shanks's square forms factorization

Key takeaways

Shanks's square forms factorization belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Shanks's square forms factorization to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Shanks's square forms factorization from memory before moving on to harder problems.

Reference excerpt

Shanks' square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The success of Fermat's method depends on finding integers x {\displaystyle x} and y {\displaystyle y} such that x 2 − y 2 = N {\displaystyle x^{2}-y^{2}=N} , where N {\displaystyle N} is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers x {\displaystyle x} and y {\displaystyle y} such that x 2 ≡ y 2 ( mod N ) {\displaystyle x^{2}\equiv y^{2}{\pmod {N}}} . Finding a suitable pair ( x , y ) {\displaystyle (x,y)} does not guarantee a factorization of N {\displaystyle N} , but it implies that N {\displaystyle N} is a factor of x 2 − y 2 = ( x − y ) ( x + y ) {\displaystyle x^{2}-y^{2}=(x-y)(x+y)} , and there is a good chance that the prime divisors of N {\displaystyle N} are distributed between these two factors, so that calculation of the greatest common divisor of N {\displaystyle N} and x − y {\displaystyle x-y} will give a non-trivial factor of N {\displaystyle N} . A practical algorithm for finding pairs ( x , y ) {\displaystyle (x,y)} which satisfy x 2 ≡ y 2 ( mod N ) {\displaystyle x^{2}\equiv y^{2}{\pmod {N}}} was developed by Shanks, who named it Square Forms Factorization or SQUFOF. The algorithm can be expressed in terms of continued fractions or in terms of quadratic forms. Although there are now much more efficient factorization methods available, SQUFOF has the advantage that it is small enough to be implemented on a programmable calculator. Shanks programmed it on an HP-65, made in 1974, which has storage for only nine digit numbers and allows only 100 steps/keystrokes of programming. There are versions of the algorithm that use little memory and versions that store a list of values that run more quickly. In 1858, the Czech mathematician Václav Šimerka used a method similar to SQUFOF to factor ( 10 17 − 1 ) / 9 {\displaystyle (10^{17}-1)/9} = {\displaystyle =} 11111111111111111 {\displaystyle 11111111111111111} = {\displaystyle =} 2071723 ⋅ 5363222357 {\displaystyle 2071723\cdot 5363222357} .

Algorithm Note This version of the algorithm works on some examples but often gets stuck in a loop. This version does not use a list. Input: N {\displaystyle N} , the integer to be factored, which must be neither a prime number nor a perfect square, and a small positive integer, k {\displaystyle k} . Output: a non-trivial factor of N {\displaystyle N} . The algorithm:

Shanks' method has time complexity O ( N 4 ) {\displaystyle O({\sqrt[{4}]{N}})} . Stephen S. McMath wrote a more detailed discussion of the mathematics of Shanks' method, together with a proof of its correctness.

Example Let N = 11111 {\displaystyle N=11111}

Q − 1 = 1 {\displaystyle Q_{-1}=1}

Here Q 5 = 25 {\displaystyle Q_{5}=25} is a perfect square, so the first phase ends. For the second phase, set Q − 1 = 25 = 5 {\displaystyle Q_{-1}={\sqrt {25}}=5} . Then:

Here P 3 = P 4 = 82 {\displaystyle P_{3}=P_{4}=82} , so the second phase ends. Now calculate g c d ( 11111 , 82 ) = 41 {\displaystyle gcd(11111,82)=41} , which is a factor of 11111 {\displaystyle 11111} . Thus, N = 11111 = 41 ⋅ 271 {\displaystyle N=11111=41\cdot 271} .

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Shanks's square forms factorization

Start with the simplest possible case. Write down what Shanks's square forms factorization claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Shanks's square forms factorization before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Shanks's square forms factorization ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Shanks's square forms factorization

In research: Shanks's square forms factorization appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Shanks's square forms factorization in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Shanks's square forms factorization is common in secondary-school and first-year university syllabi. It links to neighbouring topics Integer factorization algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Shanks's square forms factorization outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Shanks's square forms factorization in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Shanks's square forms factorization means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Shanks's square forms factorization out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Shanks's square forms factorization in simple terms?

Shanks' square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The success of Fermat's method depends on finding integers x {\displaystyle x} and y {\displaystyle y} such that x 2 − y 2 = N {\displaystyle x^{2}-y…

Why does Shanks's square forms factorization matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Shanks's square forms factorization?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Shanks's square forms factorization.