This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we continue the mathematical attacks with the NFS algorithm.
The Number Field Sieve (NFS) is currently the most efficient known factoring algorithm. Its running time depends on the size of the number to be factored but not the size of its factors. NFS based on the idea of factoring by congruent squares: given a large integer $N$, we want to find two integers $x$ and $y$ such that $x^2=y^2 (mod \ N)$. Then hopefully we have $gcd(x-y,N)$ is a non-trivial factor of $N$.
We roughly outline how NFS works. The first step of the algorithm is to choose two monic, irreducible polynomials $f_1$ and $f_2$ of small degrees $d_1$ and $d_2$. Let $m \in Z$ be a common root of the two polynomials such that $f_1(m)=f_2(m)=0 (mod \ N)$. Let $\theta_1, \theta_2 \in C$ be two complex roots of $f_1$ and $f_2$ respectively, we construct two algebraic number fields $Z[\theta_i]=Q(\theta_i)$, where $i=1,2$. Actually this gives us two number rings with multiplication defined as polynomial multiplication. Then we define the homomorphisms $\phi_i : \ Z[\theta_i] \rightarrow Z_N$, which maps $\theta_i$ to $m$ (where $i=1,2$). The NFS algorithm aims to find two squares $\gamma_1^2$ and $\gamma_2^2$ from each of the two number rings, such that $\gamma_1^2= \prod_{(a,b) \in S}(a-b\cdot \theta_1)$ and $\gamma_2^2= \prod_{(a,b) \in S}(a-b\cdot \theta_2)$, where $\gamma_1 \in Z[\theta_1]$, $\gamma_2 \in Z[\theta_2]$ and $S$ is a finite set of coprime integer pairs $(a,b)$. In order to find such a set $S$, we will sieve the elements of the form $a-b\cdot \theta_i$ for pairs of $(a,b)$ such that $a-b\cdot \theta_i$ is smooth over some algebraic factorbase. How fast we can find the set $S$ is the key to the efficiency of the algorithm. Next, we need to extract the square root of $\gamma_i^2$ to obtain $\gamma_i$, where $i=1,2$. The methods of Couveignes [1] and Montgomery [2] can be used here. Once the two square roots are calculated, we apply the homomorphisms to have $\phi_1(\gamma_1)^2 = \phi_2(\gamma_2)^2 (mod \ N)$ and expect to have $gcd(N,\phi_1(\gamma_1)-\phi_2(\gamma_2)) \neq 1$ or $N$ is a non-trivial factor of $N$.
[1] Couveignes, Jean-Marc. "Computing a square root for the number field sieve." The development of the number field sieve. Springer Berlin Heidelberg, 1993. 95-102.
[2] Montgomery, Peter L. "Square roots of products of algebraic numbers." Mathematics of Computation (1993): 567-571. APA
We roughly outline how NFS works. The first step of the algorithm is to choose two monic, irreducible polynomials $f_1$ and $f_2$ of small degrees $d_1$ and $d_2$. Let $m \in Z$ be a common root of the two polynomials such that $f_1(m)=f_2(m)=0 (mod \ N)$. Let $\theta_1, \theta_2 \in C$ be two complex roots of $f_1$ and $f_2$ respectively, we construct two algebraic number fields $Z[\theta_i]=Q(\theta_i)$, where $i=1,2$. Actually this gives us two number rings with multiplication defined as polynomial multiplication. Then we define the homomorphisms $\phi_i : \ Z[\theta_i] \rightarrow Z_N$, which maps $\theta_i$ to $m$ (where $i=1,2$). The NFS algorithm aims to find two squares $\gamma_1^2$ and $\gamma_2^2$ from each of the two number rings, such that $\gamma_1^2= \prod_{(a,b) \in S}(a-b\cdot \theta_1)$ and $\gamma_2^2= \prod_{(a,b) \in S}(a-b\cdot \theta_2)$, where $\gamma_1 \in Z[\theta_1]$, $\gamma_2 \in Z[\theta_2]$ and $S$ is a finite set of coprime integer pairs $(a,b)$. In order to find such a set $S$, we will sieve the elements of the form $a-b\cdot \theta_i$ for pairs of $(a,b)$ such that $a-b\cdot \theta_i$ is smooth over some algebraic factorbase. How fast we can find the set $S$ is the key to the efficiency of the algorithm. Next, we need to extract the square root of $\gamma_i^2$ to obtain $\gamma_i$, where $i=1,2$. The methods of Couveignes [1] and Montgomery [2] can be used here. Once the two square roots are calculated, we apply the homomorphisms to have $\phi_1(\gamma_1)^2 = \phi_2(\gamma_2)^2 (mod \ N)$ and expect to have $gcd(N,\phi_1(\gamma_1)-\phi_2(\gamma_2)) \neq 1$ or $N$ is a non-trivial factor of $N$.
[1] Couveignes, Jean-Marc. "Computing a square root for the number field sieve." The development of the number field sieve. Springer Berlin Heidelberg, 1993. 95-102.
[2] Montgomery, Peter L. "Square roots of products of algebraic numbers." Mathematics of Computation (1993): 567-571. APA
No comments:
Post a Comment