0
$\begingroup$

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.

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

For arbitrary positive integer $n$ we have:

$$\gcd(n,n+1)=1$$

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

$\endgroup$
1
$\begingroup$

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

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