Continued Fraction Factorization algorithm

26 July 2024

0

The continued fraction factorization method (CFRAC) is a general-purpose factorization algorithm valid for integers. It calculates factors of a given integer number without considering its unique properties. It has a sub-exponential running time. It was first described in 1931 by D. H. Lehmer and R. E. Powers and later in 1975 were developed into a computer algorithm by Michael A. Morrison and John Brillhart.

Continued Fraction:
An expression that can be expressed in the form:

(1) $\begin{equation*} X=a_{0}+\frac{b_{1}}{a_{1}+\frac{b_{2}}{a_{2} \ldots+\frac{b_{n-1}}{a_{n-1}+\frac{b_{n}}{a_{n}}}}} \end{equation*}$

is called a Continued Fraction, where a_i and b_iare either real or complex values for all i > = 0. When all the values of b_i‘sare 1, then it is called a simple continued fraction.

A Simple Continued Fraction can be denoted as:

(2) $\begin{equation*} \left[a_{0} ; a_{1}, a_{2} \ldots a_{n}\right]=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2} \ldots+\frac{1}{a_{n-1}+\frac{1}{a_{n}}}}} \end{equation*}$

where C_k= [a_0;a₁, a₂, …, a_n] for k<=n is the k-th convergent of the Simple Continued Fraction.
An Infinite Continued Fraction [a₀; a₁, a₂, …, a_k,…] is defined as a limit of the convergents C_k=[a0; a1, a2, …, an]

Algorithm:
This algorithm uses residues produced in the Continued Fraction of (mn)^1/2 for some m to produce a square number.

This algorithm solves the mathematical equation:

(3) $\begin{equation*} x^{2} \equiv y^{2}(\bmod (n)) \end{equation*}$

this equation is solved by calculating the value of m such that m²(mod(n)) has the minimum upperbound.

CFRAC algorithm has a time complexity of:

(4) $\begin{equation*} O\left(e^{\sqrt{2 \log n \log \log n}}\right) \end{equation*}$

Example 1:

 
Input: continued_fraction((10/7))
Output: [1, 2, 3]

Explanation:

(5) $\begin{equation*} [1,2,3]=1+\frac{1}{2+\frac{1}{3}}=1+\frac{1}{\frac{7}{3}}=1+\frac{3}{7}=\frac{10}{7} \end{equation*}$

Example 2:

Input:  list(continued_fraction_convergents([0, 2, 1, 2]))
Output: [0, 1/2, 1/3, 3/8]
Explanation:

(6) $\begin{equation*} \begin{array}{c} {[0,2,1,2]=0+\frac{1}{2+\frac{1}{1+\frac{1}{2}}}} \\ c_{1}=0, c_{2}=0+\frac{1}{2}=\frac{1}{2} \cdot c_{3}=0+\frac{1}{2+\frac{1}{1}}=\frac{1}{3} \cdot c_{4}=0+\frac{1}{2+\frac{1}{1+\frac{1}{2}}}=0+\frac{1}{2+\frac{1}{3}}=0+\frac{1}{2+\frac{1}{2}}=\frac{1}{\frac{1}{3}}=\frac{3}{8} \end{array} \end{equation*}$

Example 3:

 
Input: continued_fraction_reduce([1, 2, 3, 4, 5]) 
Output: 225/157
Explanation:

(7) $\begin{equation*} 1+\frac{1}{2+\frac{1}{3+\frac{1}{4+\frac{1}{5}}}}=1+\frac{1}{2+\frac{1}{3+\frac{1}{21}}}=1+\frac{1}{2+\frac{1}{3+\frac{5}{5}}}=1+\frac{1}{2+\frac{1}{68}}=1+\frac{1}{2+\frac{21}{68}}=1+\frac{1}{\frac{157}{68}}=1+\frac{68}{157}=\frac{225}{157} \end{equation*}$

Implementation:
Code: To convert a fraction into Continued Fraction representation

#using sympy module 
from sympy.ntheory.continued_fraction import continued_fraction 
from sympy import sqrt 
#calling continued_fraction method 
continued_fraction(10/7) 

Output:

[1, 2, 3]

Code 2: To convert a Continued Fraction into fraction.

#using sympy module 
from sympy.ntheory.continued_fraction import continued_fraction_reduce  
  
#calling continued_fraction_reduce method 
continued_fraction_reduce([1, 2, 3, 4, 5]) 

Output:

225/157

Code 3: To get a list of convergents from a Continued fraction.

# using sympy module 
from sympy.core import Rational, pi 
from sympy import S 
from sympy.ntheory.continued_fraction import continued_fraction_convergents, continued_fraction_iterator       
# calling continued_fraction_convergents method and  
# passing it as a parameter to a list 
list(continued_fraction_convergents([0, 2, 1, 2])) 