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
$\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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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