3
$\begingroup$

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.

What are the subexponential techniques that only applies to

  1. balanced semiprime integer factoring but not to discrete logarithm over some known cryptographically important structures including $\mathbb F_p^*$ and Elliptic Curve Discrete Logarithm?

  2. balanced semiprime integer factoring but not to discrete logarithm over all known cryptographically important structures including $\mathbb F_p^*$ and Elliptic Curve Discrete Logarithm?

  3. discrete logarithm over some known cryptographically important structure including $\mathbb F_p^*$ but not to balanced semiprime integer factoring?

Please provide references appropriately.

$\endgroup$

1 Answer 1

1
$\begingroup$

Lenstra's ECM method is, in the worst case ($N = pq$ with $p < q$ both primes of the same size), $L_p(1/2)$ (see H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) vol. 126 no. 3 (1987): 649-37). ECM cannot be used to solve discrete logs in elliptic curves or finite fields, so I think this answers 1. and 2.

For 3., there are subexponential finite-field-discrete-log-specific algorithms (like Adleman's Function Field Sieve, for example, or more recently the Barbulescu-Gaudry-Joux-Thomé quasipolynomial algorithm), but they apply to small- and medium-characteristic extension fields, not $\mathbb{F}_p^\times$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .