Questions tagged [sieve]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
57 views

Does the ability to factor in polynomial time give you smooth numbers in the number field sieve?

I have read that despite strong connections between prime factorization and DLP an algorithm for the former does not imply the latter directly. But I was reading about the number field sieve and it ...
Ian Campbell's user avatar
2 votes
2 answers
151 views

A variation of Sieve of Eratosthenes for random pseudoprime number generation

I wasn't sure if this question is more suited for SE.Math or not; please tell me if I should move it. For its mpz_nextprime() function (find the next pseudoprime ...
fjarri's user avatar
  • 289
0 votes
1 answer
139 views

Take n = 4633 and B = {−1, 2, 3}. Note the b-smooth numbers as {67, 68, 69}. Find the factor of n

This question is from Quadratic Sieve Factorization Method. Didn't find the solution on the web also. And not aware of how to solve such questions.
alu vaja's user avatar
2 votes
1 answer
521 views

Quadratic Sieve: Is there a thumb rule for deciding how many numbers to sieve?

In the Quadratic Sieve algorithm, we first decide on a B & then look for B-smooth prime factors by sieving using a quadratic polynomial. I can find a few formulas which help figure out how to ...
user93353's user avatar
  • 2,199
6 votes
0 answers
190 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. ...
Turbo's user avatar
  • 908
1 vote
1 answer
182 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 ...
Turbo's user avatar
  • 908
3 votes
1 answer
207 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)...
Turbo's user avatar
  • 908
3 votes
1 answer
183 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 ...
fgrieu's user avatar
  • 140k
12 votes
3 answers
2k 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 ...
fgrieu's user avatar
  • 140k