Suppose that $G=\langle g\rangle$ is a general group of order $p$. Maurer has introduced an algorithm to reduce the discrete log problem to the Diffie-Hellman problem under a conjecture about smooth numbers. Actually by the conjecture there exists an auxiliary elliptic curve $E/\mathbb{F}_p$ which help us solve the problem.In the algorithm to find $a$ from $g^a$, one should compute the point $(g^a, g^b)\in E(\mathbb{F}_p)$, where $b$ is computed in the algorithm. Hence $g^a\in \mathbb{F}_p$. I know $G\cong \mathbb{Z}_p$, but how can we convert $g^a$ to an element of $\mathbb{F}_p$? Actually, I want to implement the algorithm for the ellitpic curve discrete log problem in the group of points on the special elliptic curve $E$, for which I have found the auxiliary elliptic curve. I have a problem in computing the point. Is this algorithm applicable to the group of points on an elliptic curve?

  • 2
    $\begingroup$ Initializations: DLP = Discrete Logarithm Problem, DHP = Diffie-Hellman Problem, EC = Elliptic Curve. If these are not correct, you should correct them ASAP. (Generally, I do not find it good form to use a lot of initializations; they usually do not save knowledgeable users any time, and they cost unknowledgeable users like myself time to decipher.) $\endgroup$ – Todd Trimble May 24 '15 at 16:18
  • 1
    $\begingroup$ @Todd Is "initialization" the new term for "acronym"? :) I like it, but unfortunately initialization already has another standard meaning. (I also agree with you that on MO, one should avoid using acronyms without defining them.) $\endgroup$ – Joe Silverman May 24 '15 at 23:19
  • $\begingroup$ @JoeSilverman I probably should have said 'initialism' instead (which would also avoid the clash of meaning you observed). My understanding is that an acronym is usually something pronounced as a word (like 'laser' or 'defcon') which may or may not be an initialism, as these two examples imply. But then under this definition, something like ECDLP would be considered a pure initialism. Here's Wikipedia: en.wikipedia.org/wiki/Acronym#Nomenclature. $\endgroup$ – Todd Trimble May 24 '15 at 23:26
  • $\begingroup$ @ToddTrimble The wikipedia article says "Although the word acronym is widely used to refer to any abbreviation formed from initial letters some dictionaries and usage commentators define acronym to mean..." Personally, I don't see the need to distinguish between the two, but I guess that one could come up with a situation where one might want to make the distinction. Chacun a son ... $\endgroup$ – Joe Silverman May 25 '15 at 1:19
  • $\begingroup$ @JoeSilverman Perhaps I should not have said "usually". All I really meant in my last comment was to explain my own preferred word usage. $\endgroup$ – Todd Trimble May 25 '15 at 1:45

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.