# Questions tagged [sieve]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
• 289
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.
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 ...
• 2,199
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. ...
• 908
1 vote
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 ...
• 908