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 cryptographically important structures including $\mathbb F_p^*$ and Elliptic Curve Discrete Logarithm?

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

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

Please provide references appropriately.

$\endgroup$
  • 1
    $\begingroup$ Index Calculus and Elliptic Curve Factoring. $\endgroup$ – SEJPM Jul 22 at 19:16
  • $\begingroup$ @SEJPM I thought index calculus is sieve technique for discrete logarithm. $\endgroup$ – T.... Jul 22 at 19:21
  • 1
    $\begingroup$ Index calculus indeed works for DLP. $\endgroup$ – forest Jul 22 at 19:25
  • 1
    $\begingroup$ What about the algebraic factoring algorithms such as the Pollard $p-1$ and Williams $p+1$ (which are efficient when the underlying primes are smooth)? I am not aware of their counterparts in the discrete-log setting. $\endgroup$ – Occams_Trimmer Jul 23 at 8:48
  • $\begingroup$ @Occams_Trimmer Possible. $\endgroup$ – T.... Jul 23 at 21:57

Your Answer

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

Browse other questions tagged or ask your own question.