1
$\begingroup$

While implementing the Quadratic Sieve, the textbooks give a rough formula for what Smoothness bound you should use in your Factor Base.

To factor a number N using the Quadratic Sieve, we can use the following:

$L = e^{\sqrt {\ln(N)ln(ln(N))}}$, $B = L^{\frac {1}{\sqrt 2}}$

For the Index Calculus method for solving the Discrete Log problem in $\mathbb F_p$, is there a similar formula? Many of the texts I checked, just say choose an appropriate Smoothness Bound B. But don't give any indication of how one chooses an appropriate B.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
+50
$\begingroup$

Coppersmith, Odlyzko, and Schroeppel originally set $B = L[1/2, 1/2]$ for both the linear and Gaussian sieves. Pomerance set $B = L[1/2, 1/\sqrt{2}]$ for a rigorous index calculus variant using the elliptic curve method as the smoothness testing method.

These bounds are only asymptotic; the bound in an implementation will usually be adjusted to account for the real non-asymptotic performance of the involved subroutines.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I tried this formula with some solved examples in some books & the result seems quite off from what the examples have used. For e.g. in Silverman's mathematical cryptography book, he solves $37^x \equiv 211 \pmod 18443$. If I use the $B = L^{\frac {1}{\sqrt 2}}$ formula, I get 28.5. However, to solve the problem, Silverman uses B=5 which is quite far off from the calculated B. Silverman also has an exercise problem $17^x \equiv 19 \pmod 19079$, where B calculated would be 28.5, but I am able to solve it again using B=5. $\endgroup$
    – user93353
    Aug 27, 2021 at 1:19
  • $\begingroup$ What do you mean by ` with early aborts, as the smoothness tester.`? $\endgroup$
    – user93353
    Aug 27, 2021 at 1:20
  • $\begingroup$ Why are there 2 formulas i.e. why $B = L[1/2, 1/\sqrt{2}]$ - what is the $L^{1/2}$ $\endgroup$
    – user93353
    Aug 27, 2021 at 1:25
  • $\begingroup$ If you're looking at Silverman's book, the end of Section 3.8 in page 169 would have answered your question. Don't pay much attention to the parameters in the examples, those are optimized for clarity rather than performance (i.e., it would look worse for a worked example to have too many primes, lots more relations needed etc.) $\endgroup$
    – Samuel Neves
    Aug 27, 2021 at 3:30
  • $\begingroup$ $L[1/2, 1/\sqrt{2}]$ is the more general L-notation. It means the same as your $L^{1/\sqrt{2}}$. $\endgroup$
    – Samuel Neves
    Aug 27, 2021 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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