Kraitchik's Factor Base Method

The Kraitchik factorization method aims to find two distinct integers $ x \neq y $ such that $ x^2 > n $ and $ x^2 \equiv y^2 \pmod{n} $. Once such a pair is identified, we compute the greatest common divisor (GCD) of $ n $ and $ x - y $ (or $ x + y $) to extract a non-trivial factor of $ n $.

How does it work?

Here’s a step-by-step breakdown of the method for factoring $ n $:

Find the smallest integer $ x $ such that $ x^2 > n $.
Determine an integer $ y $ such that $ x^2 \equiv y^2 \pmod{n} $, meaning that $ x^2 $ and $ y^2 $ are congruent modulo $ n $.
Compute $ x - y $ and $ x + y $.
Calculate the greatest common divisor (GCD) of $ n $ and one of these values: \[ GCD(n, x - y) \quad \text{or} \quad GCD(n, x + y) \]
If the resulting GCD is a non-trivial factor of $ n $ (i.e., not 1 or $ n $), we have successfully found a factor of $ n $. To continue, divide $ n $ by this factor.
If the factor is composite, keep factorizing until only prime factors remain.

This procedure ultimately decomposes $ n $ into its prime factors.

Note. This method generalizes Fermat’s factorization technique. Rather than solving $ x^2 - y^2 = n $ directly, it relies on the congruence $ x^2 \equiv y^2 \pmod{n} $, which is equivalent to $ x^2 - y^2 \equiv 0 \pmod{n} $. Since $ x^2 - y^2 $ can be rewritten as $ (x - y)(x + y) $, finding distinct $ x $ and $ y $ satisfying this condition implies that $ n $ divides the product $ (x - y)(x + y) $. This guarantees that at least one of $ x - y $ or $ x + y $ shares a non-trivial factor with $ n $.

A Practical Example
Finding x and y Using Factorization Bases
Notes

A Practical Example

Let’s factorize $ n = 1001 $ using Kraitchik’s method.

We need to find two numbers $ x $ and $ y $ such that:

$$ x^2 \equiv y^2 \pmod{1001} $$

First, we estimate $ \sqrt{1001} $:

$$ \sqrt{1001} \approx 31.6 $$

Since $ x $ must be greater than 31, we start our search from $ x > 31 $.

Choosing $ x = 71 $, we compute its square modulo 1001:

\[ 71^2 \equiv 36 \pmod{1001} \]

How do you determine x and y? To find the optimal values for $ x $ and $ y $, the key is identifying the best factorization base. I’ll cover that in the next section. For now, I'll use $ x = 71 $ and $ y = 6 $, since I already know these values are valid. This allows me to better illustrate how Kraitchik’s method works.

Since $ 36 $ is a perfect square ($ \sqrt{36} = 6 $), we set:

$$ x = 71, \quad y = 6 $$

These values satisfy the key congruence:

\[ x^2 \equiv y^2 \pmod{1001} \]

Now, we compute $ GCD(n, x - y) $:

\[ x - y = 71 - 6 = 65 \]

Using the Euclidean algorithm to compute $ GCD(65, 1001) $:

\[ 1001 = 65 \times 15 + 26 \]

\[ 65 = 26 \times 2 + 13 \]

\[ 26 = 13 \times 2 + 0 \]

Since the last nonzero remainder is 13, we conclude:

\[ GCD(65, 1001) = 13 \]

Since 13 is a non-trivial factor of 1001, we proceed by dividing:

\[ \frac{1001}{13} = 77 \]

Since 77 is composite, we continue factorizing:

\[ 77 = 7 \times 11 \]

Thus, the full prime factorization of 1001 is:

\[ 1001 = 13 \times 7 \times 11 \]

Note. Instead of using $ x - y $, we could have used $ x + y $. For instance, with $ x = 71 $ and $ y = 6 $: $$ x + y = 71 + 6 = 77 $$ Computing $ GCD(77, 1001) $: $$ GCD(77, 1001) = 11 $$ This gives another non-trivial factor, $ 11 $. We then divide $ 1001 $ by $ 11 $: $$ \frac{1001}{11} = 91 $$ Since $ 91 $ is composite, we factor it further: $$ 91 = 7 \times 13 $$ Thus, the complete factorization remains: \[ 1001 = 13 \times 7 \times 11 \] No matter which approach we take, the result is always the same.

Finding x and y Using Factorization Bases

To determine a suitable factorization base, you can use the following formula:

\[ b_k = \lfloor \sqrt{n \cdot k} \rfloor + 1, \quad k = 1, 2, 3, \dots \]

This generates a sequence of candidate values $ b_k $ that can be tested using modular squaring:

\[ b_k^2 \mod n \]

Once you compute $ b_k^2 \mod n $, attempt to factor it into its prime components.

If $ b_k^2 \mod n $ happens to be a perfect square, you can apply Kraitchik’s factorization method by setting $ x = b_k $ and $ y = \sqrt{ b_k^2 \mod n } $.

What if I don’t get a perfect square? If none of the $ b_k^2 \mod n $ values are perfect squares outright, you’ll need to combine multiple values to construct one. This involves working with $ B $-vectors and reducing them modulo 2.

Generate a set of $ b_k $ values using the formula: \[ b_k = \lfloor \sqrt{n \cdot k} \rfloor + 1 \]
Compute $ b_k^2 \mod n $ for each one.
Factorize each $ b_k^2 \mod n $ into its prime components.
Choose a factor base $ B = \{p_1, p_2, \dots\} $ consisting of small primes.
Construct the corresponding $ B $-vectors, where each exponent is reduced modulo 2 (even exponents become 0, odd exponents become 1).
Find a linear combination of these vectors that sums to zero modulo 2. If such a combination exists, it means the product of the corresponding numbers forms a perfect square.
Once you’ve identified a perfect square modulo $ n $, compute the greatest common divisor: \[ \gcd(n, b - c) \]
If this yields a non-trivial factor of $ n $, you’ve successfully factored the number. If instead you get $ n $ or $ 1 $ (trivial factors), you’ll need to retry with a different combination.

Example

Let's factorize $ n = 1001 $.

The first candidate base, for $ k = 1 $, is:

\[ b_1 = \lfloor \sqrt{1001 \cdot 1} \rfloor + 1 = 32 \]

Next, we compute $ b_1^2 $ modulo $ n $:

\[ 32^2 \equiv 23 \pmod{1001} \]

The prime factorization of 23 is simply $ 23^1 $, since 23 itself is prime. This is not a perfect square, so we proceed to the next base.

For $ k = 2 $:

\[ b_2 = \lfloor \sqrt{1001 \cdot 2} \rfloor + 1 = 45 \]

Computing $ b_2^2 $ modulo $ n $:

\[ 45^2 \equiv 23 \pmod{1001} \]

Again, the result is $ 23^1 $, which is not a perfect square.

For $ k = 3 $:

\[ b_3 = \lfloor \sqrt{1001 \cdot 3} \rfloor + 1 = 55 \]

Checking whether $ b_3^2 $ forms a perfect square:

\[ 55^2 \equiv 22 \pmod{1001} \]

Factorizing $ 22 $ gives $ 2^1 \cdot 11^1 $, which is still not a perfect square.

For $ k = 4 $:

\[ b_4 = \lfloor \sqrt{1001 \cdot 4} \rfloor + 1 = 64 \]

\[ 64^2 \equiv 92 \pmod{1001} \]

Factorizing $ 92 $ gives $ 2^2 \cdot 23^1 $, which is also not a perfect square.

For $ k = 5 $:

\[ b_5 = \lfloor \sqrt{1001 \cdot 5} \rfloor + 1 = 71 \]

\[ 71^2 \equiv 36 \pmod{1001} \]

The factorization of $ 36 $ is:

\[ 3^2 \times 2^2 = (3 \times 2)^2 = 6^2 \]

This time, we have a perfect square.

Since $ b_5 $ produces a perfect square, we can now apply Kraitchik’s method, setting $ x = 71 $ and $ y = 6 $.

We compute:

\[ x - y = 71 - 6 = 65 \]

Now, we find the greatest common divisor:

\[ \gcd(1001, 65) = 13 \]

This gives us a non-trivial factor of $ n = 1001 $. To find the remaining factors, we divide $ n $ by 13:

\[ \frac{1001}{13} = 77 = 7 \times 11 \]

Thus, the complete prime factorization of $ 1001 $ is:

\[ 1001 = 13 \times 7 \times 11 \]

Example 2

What if we don’t find a perfect square? In this case, we need to construct the $ B $-vectors for each attempt.

For instance, let's attempt to factorize $ n = 2183 $.

b_k	b_k² mod 2183	Fattorizzazione
47	26	2¹ × 13¹
67	123	3¹ × 41¹
81	12	2² × 3¹
94	104	2³ × 13¹
105	110	2¹ × 5¹× 11¹
124	95	5¹× 19¹
133	225	3²× 5²
141	234	2¹× 3²× 13¹
148	74	2¹× 37¹
155	12	2² × 3¹
162	48	2⁴× 3¹
169	182	2¹× 7¹ × 13¹
175	63	3²× 7¹
181	16	2⁴

The last value found ($ b_k = 181 $) is a perfect square since:

\[ 181^2 \equiv 16 \pmod{2183} \]

Thus, we can directly apply Kraitchik’s method.

Example. Given that we’ve found a perfect square, we set $ x = 181 $ and $ y = \sqrt{16} = 4 $, and compute: \[ x - y = 181 - 4 = 177 \] Next, we find: \[ \gcd(2183, 177) = 59 \] This yields a non-trivial factor of 2183. To obtain the remaining factor, we divide: \[ \frac{2183}{59} = 37 \] Thus, the complete factorization is: \[ 2183 = 37 \times 59 \]

However, the purpose of this example is to demonstrate that even if we don’t find a perfect square directly, we can construct one by combining different $ b_k $ values.

This approach is particularly useful when no single $ b_k $ immediately produces a perfect square.

First, we observe that many numbers share the smallest prime factors, 2 and 3. So, we use the factorization base $ B(2,3) $.

It’s generally best to start with the smallest primes and expand the base as needed.

Next, we compute the $ B $-vectors modulo 2 for all $ b_k $ values that contain only 2 and/or 3 as prime factors, ignoring the others.

b_k	b_k² mod 2183	Fattorizzazione	B-vettore	B-vettore ridotto modulo 2
47	26	2¹ × 13¹
67	123	3¹ × 41¹
81	12	2² × 3¹	(2² , 3¹)	(0 , 1)
94	104	2³ × 13¹
105	110	2¹ × 5¹× 11¹
124	95	5¹× 19¹
133	225	3²× 5²
141	234	2¹× 3²× 13¹
148	74	2¹× 37¹
155	12	2² × 3¹	(2² , 3¹)	(0 , 1)
162	48	2⁴× 3¹	(2⁴ , 3¹)	(0 , 1)
169	182	2¹× 7¹ × 13¹
175	63	3²× 7¹
181	16	2⁴	(2⁴ , 3⁰)	(0 , 0)

At this stage, we seek a combination of vectors that sum to (0,0) modulo 2.

Example. The perfect square $ b = 181 $ already has a zero vector (0,0) in $ B(2,3) $, but we’re looking for an alternative combination.

For example, the $ B $-vectors for 81 and 155 sum to zero modulo 2:

\[ (0,1)_{81} + (0,1)_{155} \mod 2 = (0+0, 1+1) = (0,0) \]

The corresponding product is:

\[ 81 \times 155 = 12555 \equiv 1640 \pmod{2183} \]

Since:

\[ 1640^2 \equiv 144 \pmod{2183} \]

And 144 is a perfect square ($ 12^2 $), we can proceed with the factorization.

\[ \gcd(2183, 1640 - 12) = \gcd(2183, 1628) = 37 \]

Thus, we’ve found a prime factor of 2183: $ 37 $.

To find the remaining factor, we divide:

\[ \frac{2183}{37} = 59 \]

So, the complete factorization is:

\[ 2183 = 37 \times 59 \]

We’ve reached the same result, but through an indirect approach.

What if we don’t find a non-trivial factor? In this case, we need to look for another combination of $ B $-vectors that sum to (0,0) modulo 2. If no valid combination is found after several attempts, we can generate additional $ b_k $ values. If necessary, we can also modify the factorization base $ B $ by including an additional prime.

Notes

Some key insights and considerations regarding this method.

When Kraitchik’s method fails: the case $ x \equiv \pm y \pmod{n} $
A fundamental limitation of Kraitchik’s factorization method arises when all prime factors of $ n $ divide only one of the two expressions, $ x - y $ or $ x + y $. In such cases, we encounter the congruence: \[ x \equiv \pm y \pmod{n} \] This condition renders the method ineffective, as it fails to reveal any useful information about the factors of $ n $. Instead, we must search for an alternative pair of values $ x $ and $ y $ that avoid this scenario. Consider, for example, the composite number $ 91 = 7 \times 13 $ and attempt to apply Kraitchik’s method to factorize it. Suppose we select the integer pair: \[ x = 46, \quad y = 45 \] These values satisfy the key congruence: \[ 46^2 \equiv 45^2 \pmod{91} \] However, in this case, we run into a fundamental issue because: \[ 46 \equiv -45 \pmod{91} \] Since $ x \equiv -y \pmod{91} $, the method fails to provide a non-trivial factor of $ n $. Instead, it produces only trivial factors: \[ x - y = 46 - 45 = 1 \] and \[ GCD(91, 1) = 1, \] which is a trivial divisor of 91.
How to mitigate this issue? To ensure that the method yields a non-trivial factor of $ n $, it is crucial to select $ x $ and $ y $ such that: \[ x \not\equiv \pm y \pmod{n} \] This guarantees that at least one prime factor of $ n $ divides $ x - y $, while a different prime factor divides $ x + y $. Recognizing and addressing this constraint is essential for the correct application of Kraitchik’s factorization method.