Join Log in
Score:1
avatar Crypto

How to choose the appropriate Smoothness Bound while using the Index Calculus method

et flag
user93353

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.

117
1 + 0
Score:1
avatar Crypto
pe flag
Samuel Neves

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.

0 + 7
et flag
user93353
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.
0
Reply
et flag
user93353
What do you mean by ` with early aborts, as the smoothness tester.`?
0
Reply
et flag
user93353
Why are there 2 formulas i.e. why $B = L[1/2, 1/\sqrt{2}]$ - what is the $L^{1/2}$
0
Reply
pe flag
Samuel Neves
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.)
0
Reply
pe flag
Samuel Neves
$L[1/2, 1/\sqrt{2}]$ is the more general [L-notation](https://en.wikipedia.org/wiki/L-notation). It means the same as your $L^{1/\sqrt{2}}$.
0
Reply
et flag
user93353
Thank you - can you also let me know what you mean by `with early aborts, as the smoothness tester.`
0
Reply
pe flag
Samuel Neves
Nevermind that, I confused this with another Pomerance paper. Here it's just ECM. But that does not matter too much; trial division will also work, with a somewhat worse runtime.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.