Questions tagged [sieve]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
0answers
166 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
1
vote
1answer
137 views

Quadratic sieve for DLOG performance - theory vs actual?

Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes? Is actual data better than theory in any way unexplained (I ...
3
votes
1answer
133 views

Combining Hellman Pohlig with Sieve

Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes. Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)...
3
votes
1answer
143 views

Proportion of RSA moduli factorable by NFS with less effort than average?

When applied to integers $N$ of comparable size, the Number Field Sieve is notoriously much faster if $N$ is known to be of the form $r^k\pm s$ with $r$ and $s$ suitably small integers, and $k$ an ...
9
votes
2answers
1k views

In the Quadratic Sieve, why restrict the factor base?

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...