# Tag Info

## Hot answers tagged sieve

3

I'm not sure if I understand the question correctly, but let's try anyway. By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$. We note that $\mathbb{Z}_m^*$ is a ...

2

To my knowledge, there are two reports that deal with the crossover point between the Gaussian integer sieve—which is the rough analogous of the quadratic sieve for discrete logarithms—and the number field sieve over prime fields: Weber (1998) computed discrete logarithms over a 85-digit (~283 bits) prime, and concluded that at that size point the Gaussian ...

2

Answering my own question, with some degree of uncertainty. The basic Quadratic Sieve (as in Wikipedia's algorithm and the example quoted in the question) finds smooth integers among $x^2\bmod N$, for $x$ starting at $\lceil\sqrt N\rceil$. Until $x$ reaches $\lceil\sqrt{2N}\rceil$, it is searched smooth numbers among $x^2-N$. If this is divisible by a prime ...

2

The condition $\genfrac(){}{}{a}{b}$=+1 doen't matter as the product of 2 QNR is a QR.In fact the idea of locking for numbers satisfying $x^2-y^2=k.n$ was firstly introduced by Gauss (1801) and was developped by Kraichick (1920) by searching for special sequences of the form $Q(x_i)=x_i^2 -n$ which factorize over small primes $\prod Q(x_i)=v^2$. In the ...

2

The core difference between the SNFS and the GNFS is that the polynomials $f(x)$ and $g(x)$ for the SNFS have short coefficients, where typically the largest coefficient of $f$ is $O(1)$ and the largest coefficient of $g$ is $O(n^{1/(d + 1)})$. On the GNFS, coefficients are typically closer to $n^{1/(d+1)}$ on both sides, which results in much larger ...

1

I believe Carl Pomerance (the inventor of the quadratic sieve algorithm) gives a great explanation in: Pomerance, C. (2008). Smooth numbers and the quadratic sieve. In Algorithmic Number Theory Lattices, Number Fields, Curves and Cryptography (pp. 69-81). Cambridge: Cambridge University Press. The quote below comes from page 72. "A number ...

Only top voted, non community-wiki answers of a minimum length are eligible