Yesterday,I took an exam. There are two questions I received very low points. I will write the first question in this post.

The question says let $E:y^2:x^3+kx+1$ in GF(p) be an elliptic curve where p is a prime number which is 512 bits long. Now, think another prime number b with same size that of p (it means b is a prime integer of size 512 bits), and there is a point on curve such that $P(0,1)$. Assume that $P(0,1) \in E[b]$. It is wanted to write a pseudo code of a method which gives other elements of $E[b]$.

What I wrote in answer:

Choose a random integer k such that $1 \leq k \leq b-1$

Compute the point $R = kP$ using point multiplication

If R is the identity element of the group, go back to step 1

Return R as an element of ($E[b]$)

I have received very low point from this answer. Because of there is no any answer paper, I dont know the correct way. Can you please help for writing the correct answer ? WHat is the algorithm ? I think my pseudo code was fine, but it is not.


1 Answer 1


It is absolutely your lecturer's/professor's responsibility to give feedback on what's wrong with your answer. We don't know what is the assumed knowledge for the course, what level of pseudocode is required, etc.

Therefore what I say below may not apply given the level expected from you:

What is the definition of $E[b]$?

Some more brief thoughts:

What you wrote does not look like pseudocode. Where is step 1? You refer to it but it's unspecified.

Do you define a loop? You are trying to hit the identity again and again for different random $k$, but the output is when you don't hit the identity? It's all extremely unclear.

  • 1
    $\begingroup$ $E[b]$ is b-torsion group $\endgroup$
    – kelalaka
    Apr 10 at 17:15
  • $\begingroup$ @kelalaka yes, you are right $\endgroup$
    – user115992
    Apr 10 at 17:54
  • $\begingroup$ I stated that I dont have answer paper,so I am here for learning. you can be advanced however you want.but please don write unnecessary statements like "Where is step 1? " as you see in my post, ı wrote the process from above to below $\endgroup$
    – user115992
    Apr 10 at 17:56
  • $\begingroup$ You should check that $P$ is not the identity. If so, it can only generate the trivial groups, otherwise the whole $E[b]$. since the $b$ is prime. Next is, $P, [2]P, [3]P. \ldots, [b]P$ are those elements/ $\endgroup$
    – kelalaka
    Apr 10 at 18:02
  • 1
    $\begingroup$ @juniorstudent Things like not putting numbers in front of the steps and such can be seen as extremely sloppy, and this can bite you when grades are delivered. I mean, it's not just that your question isn't capitalized, the very first word is spelled incorrectly as well. Precision is important for mathematicians, developers and by extension also cryptographers. Practice makes perfect. $\endgroup$
    – Maarten Bodewes
    Apr 10 at 22:05

Your Answer

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