2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ This is off-topic because it is about mathematics. $\endgroup$ – fkraiem Mar 2 '15 at 20:50
  • 3
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Mar 3 '15 at 16:10
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.