In this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem", author mentions (page 56),

For each $p_l^{e_l} | q$ proceed....

$p_l^{e_l}$ is one of the prime factors of $q-1$, and $q$ is a prime.

How can any number divide prime? Am I missing something here?

Edit1: $q$ is prime, so we can't get any non-trivial factor of $q$. Keeping this in mind, can anyone explain how to proceed with the steps mentioned in the paper. One thing to keep in mind is that $q$ has to be prime to be used in Diffie-Hellman system.

  • 4
    $\begingroup$ Presumably it's a typo and $q-1$ is meant, not $q$. $\endgroup$
    – fkraiem
    Commented Feb 14, 2016 at 5:09
  • $\begingroup$ @fkraiem. Can you direct me to any source that says that it's a typo? $\endgroup$
    – Anurag
    Commented Feb 15, 2016 at 11:17

2 Answers 2


For arbitrary positive integer $n$ we have:


So $q-1$ and $q$ haven't any nontrivial common factor.


It probably divides $q-1$ (composite) not $q$.


Your Answer

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

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