*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 (

We roughly outline how

[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

**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

## No comments:

## Post a Comment