# How to choose the integer m in the general number field sieve (GNFS)?

Given an integer you want to factor $N$, GNFS starts by selecting a monic irreducible polynomial $f \in \mathbb{Z}[X]$ and an integer $m$ such that $f(m) \equiv 0 \text{ mod } N$. In practice, if $m$ is chosen first then $f$ can just be chosen to be the $m$-base expansion of $n$, which is simple to compute. But how is $m$ chosen relative to N?

• This is off-topic because it is about mathematics. – fkraiem Mar 2 '15 at 20:50
• While this question would be on topic for Mathematics (as it does not use any crypto-specific terminology), I'd say it's also sufficiently closely related to crypto (seeing as it's essentially about optimizing a cryptanalytic attack on RSA) to be borderline on topic here as well. – Ilmari Karonen Mar 3 '15 at 16:10

For anyones who's interested - From this paper

http://scholar.lib.vt.edu/theses/public/etd-32298-93111/materials/etd.pdf

I found that it's best to find the degree of the polynomial you're going to be using based on the number of bits in $N$. Let k = $log_2N$ Briggs gives experimental bounds

$d= 5$ for $k \geq 110$

$d= 4$ for $80 > k > 110$

$d= 3$ for $50 > k \geq 80$

And doesn't say for $k \leq 50$, probably because GNFS is not the fastest for numbers that small.

Then you pick a $m$ such that $m^d$ is close to $N$. Then you find the base $m$ expansion of $N$ and obtain $f$ from that. This guarantees that $f(m) \equiv 0$ mod $N$