Continued Fraction Method for Factorization
The continued fraction method for integer factorization exploits the continued fraction expansion of \( \sqrt{n} \) to identify numbers satisfying a quadratic congruence \( b^2 \equiv c^2 \mod n \). Once such a relation is established, the greatest common divisor (GCD) can be used to extract a non-trivial factor of \( n \): $$ \gcd(b \pm c, n) $$
In essence, this method cleverly leverages the periodic nature of continued fractions associated with \( \sqrt{n} \) to uncover a congruence of the form \( b^2 \equiv c^2 \mod n \). The factorization is then achieved by computing \( \gcd(b - c, n) \), which, if non-trivial, reveals a divisor of \( n \).
How does it work?
The key steps in the continued fraction factorization method are as follows:
- Compute the integer part of \( \sqrt{n} \): $$ a_0 = \lfloor \sqrt{n} \rfloor $$
- Initialize the recurrence relations for the convergents: $$ u_0 = 1 , \quad u_1 = a_0 , \quad v_0 = 0 , \quad v_1 = 1 $$
- Compute the sequence of convergents \( C_k = \frac{u_k}{v_k} \)
- Reduce the numerators \( u_k \) modulo \( n \): \[ u_k' = u_k \mod n \]
- Determine the least absolute residue of \( u_k^2 \) modulo \( n \): \[ a_k = \text{MRA}(u_k^2, n) \]
- Identify a suitable factor base by analyzing the distribution of small prime factors
- Construct a quadratic congruence of the form \( b^2 \equiv c^2 \mod n \)
- Extract a non-trivial factor of \( n \) using the greatest common divisor: \( \gcd(b - c, n) \).
Note: The fundamental idea is to find a value of \( b \) such that: \[ b^2 \equiv c^2 \mod n \] This congruence allows us to extract a divisor of \( n \) via: \[ \gcd(b - c, n) \] If the GCD is greater than 1 and less than \( n \), we have successfully factored \( n \).
The method is effective because the numerators of the continued fraction convergents of \( \sqrt{n} \) tend to exhibit small quadratic residues modulo \( n \), making it easier to construct the desired congruence.
Note: This approach is particularly well-suited for factoring semiprimes (products of two primes of similar magnitude). It performs efficiently when \( n \) is large but not excessively so—typically in the range of a few hundred to a few thousand digits.
Despite its limitations, this technique remains a cornerstone in computational number theory.
A Practical Example
Let's apply the continued fraction method to factorize the integer \( n = 2041 \).
We begin by computing \( \sqrt{n} \) and extracting its integer part:
$$ a_0 = \lfloor \sqrt{n} \rfloor = \lfloor \sqrt{2041} \rfloor = \lfloor 45.17 \rfloor = 45 $$
Next, we construct the continued fraction expansion of \( \sqrt{2041} \), using the recursive formulas:
\[ a_k = \lfloor \frac{a_0 + m_k}{d_k} \rfloor \]
where we initialize:
\( m_0 = 0 \), \( d_0 = 1 \), and compute subsequent values via:
\[ m_k = d_{k-1} a_{k-1} - m_{k-1} \]
\[ d_k = \frac{n - m_k^2}{d_{k-1}} \]
The first few terms in the continued fraction expansion are:
| k | m_k | d_k | a_k |
|---|---|---|---|
| 0 | 0 | 1 | 45 |
| 1 | 45 | 16 | 5 |
| 2 | 35 | 51 | 1 |
| 3 | 16 | 35 | 1 |
| 4 | 19 | 48 | 1 |
| 5 | 29 | 25 | 2 |
| 6 | 21 | 64 | 1 |
Derivation: For \( k = 1 \), we compute: \[ m_1 = d_0 a_0 - m_0 = 1 \cdot 45 - 0 = 45 \] \[ d_1 = \frac{n - m_1^2}{d_0} = \frac{2041 - 45^2}{1} = 2041 - 2025 = 16 \] \[ a_1 = \lfloor \frac{a_0 + m_1}{d_1} \rfloor = \lfloor \frac{45 + 45}{16} \rfloor = \lfloor \frac{90}{16} \rfloor = 5 \] Similarly, for \( k = 2 \): \[ m_2 = d_1 a_1 - m_1 = 16 \cdot 5 - 45 = 80 - 45 = 35 \] \[ d_2 = \frac{n - m_2^2}{d_1} = \frac{2041 - 35^2}{16} = \frac{2041 - 1225}{16} = \frac{816}{16} = 51 \] \[ a_2 = \lfloor \frac{a_0 + m_2}{d_2} \rfloor = \lfloor \frac{45 + 35}{51} \rfloor = \lfloor \frac{80}{51} \rfloor = 1 \]
Thus, the continued fraction sequence begins:
$$ a_k = [ 45, 5, 1, 1, 1, 2, 1, \dots ] $$
Computing the Convergents
We initialize:
$$ u_0 = 1, \quad u_1 = a_0 = 45, \quad v_0 = 0, \quad v_1 = 1 $$
The recurrence relations yield:
\[ u_k = a_k u_{k-1} + u_{k-2} \]
\[ v_k = a_k v_{k-1} + v_{k-2} \]
The first few convergents are:
\[ \begin{array}{c|ccccc} k & 1 & 2 & 3 & 4 & 5 \\ \hline u_k & 45 & 226 & 271 & 497 & 768 \\ v_k & 1 & 5 & 6 & 11 & 17 \\ \end{array} \]
Finding a Quadratic Congruence
We compute:
\[ u_k' = u_k \mod 2041 \]
\[ \begin{array}{c|ccccc} k & 1 & 2 & 3 & 4 & 5 \\ \hline u_k' & 45 & 226 & 271 & 497 & -768 \\ M_k & -16 & 51 & -35 & 48 & -25 \\ \end{array} \]
We seek an \( M_k \) that is a perfect square modulo \( n \). In this case, we identify:
$$ M_1 = -16 = -1 \cdot 2^4 $$
$$ M_5 = -25 = -1 \cdot 5^2 $$
Defining the factor base:
$$ B = \{ 2, 5 \} $$
We construct the quadratic congruence:
$$ b^2 \equiv c^2 \pmod{n} $$
where \( b \) is the product of the corresponding values \( u'_k \), specifically \( u'_1 \cdot u'_5 \), modulo \( n = 2041 \)
$$ b = (u'_1 \cdot u'_5) \mod 2041 = (45 \cdot -768) \equiv 1904 \pmod{2041} $$
and \( c \) is the product, modulo \( n = 2041 \), of the respective bases of the perfect squares: \( M_1 = -16 = (2^2)^2 \) and \( M_5 = -25 = -1 \cdot 5^2 \), which simplifies to \( 2^2 \) and \( 5 \).
$$ c = 2^2 \cdot 5 \equiv 20 \pmod{2041} $$
Computing the greatest common divisor:
$$ \gcd(b - c, n) = \gcd(1904 - 20, 2041) = \gcd(1884, 2041) = 157 $$
Note: If this yielded a trivial factor (1 or \( n \)), we could try: $$ \gcd(b + c, n) = \gcd(1924, 2041) = 13 $$
Thus, we have successfully factored \( 2041 \) as:
$$ 2041 = 13 \times 157 $$
The prime factors of \( 2041 \) are \( 13 \) and \( 157 \).
Limitations of the Method
The continued fraction method has several significant drawbacks, which is why it has largely been superseded by more advanced factorization algorithms.
- Inefficient for large numbers
While it performs reasonably well for numbers up to 30-40 digits, it becomes impractical for larger values. The primary bottleneck is the need to compute a large number of continued fractions before identifying a valid quadratic congruence \( b^2 \equiv c^2 \mod n \). This results in a computational complexity that scales quadratically with the number of digits. - Success is not guaranteed
Even when a valid quadratic congruence is found, there is no guarantee that it will yield a useful factorization. If \( \gcd(b - c, n) \) evaluates to 1 or \( n \), no progress is made, and additional convergents must be tested, increasing computational overhead. - Works best when factors are of similar size
The method is most effective when \( n \) is the product of two primes of roughly equal magnitude. If \( n \) has highly unbalanced factors (one small, one very large), the continued fraction convergents tend to grow too rapidly, making the method far less practical. - Preprocessing is computationally intensive
The method involves several intricate preparatory steps: computing the continued fraction expansion, identifying the convergents, reducing quadratic residues, selecting an appropriate factor base, and constructing a suitable congruence. Only after all this effort can we attempt to extract a factor of \( n \), and even then, success is not assured.
In summary, while historically significant, the continued fraction method has been rendered obsolete by modern approaches. Its inherently sequential nature makes it poorly suited for parallelization, limiting its effectiveness on high-performance computing architectures.
Note: More advanced methods such as the Quadratic Sieve and the General Number Field Sieve (GNFS) are vastly superior in terms of scalability and efficiency. The Quadratic Sieve is particularly well-suited for medium-sized numbers, whereas the GNFS is the method of choice for factoring extremely large integers.
Additional Insights
Here are some additional notes on the continued fraction factorization method:
- Who developed this method?
The technique is rooted in ideas from Legendre and Gauss but was formally adapted for integer factorization by D. H. Lehmer and other 20th-century mathematicians. It shares similarities with Dixon’s method and the Quadratic Sieve, both of which represent more sophisticated approaches to factorization. - Why is it no longer in use?
Due to the advent of more efficient computational techniques, the continued fraction method has fallen out of practical use. However, it remains an important theoretical foundation for understanding modern factorization strategies such as the Quadratic Sieve.
And so on.
