If I have an elliptic curve $E$ over some finite field $F_p$ what is a step by step algorithm to pick a random point that lays on this curve? There is definitely a naive approach to brute force all possible points and check whether they lay on the curve or not, but I do not think it is optimal
5
-
$\begingroup$ Hí, R. Artur. I feel your problem could be very difficult in many cases because "finite field" means in general not infinite but it could be very big having $p^n$ elements. You do have anyway the following: $$\begin{cases}1)\space x\in\mathbb F_ {p^n}\iff x^{p^n}=x\\2)\space\text {For all primitive root }(p^n-1)-th \text { de la unidad }\alpha\text { one has }\mathbb F_ {p^n}=\mathbb F_p(\alpha)\\3)\space\mathbb F_ {p^n}^* \text { is cyclic }\\ 4)\space \mathbb F_{p^n}|\mathbb F_p\text { is a cyclic extension and } x\to x^p\text { is a canonic generator of its Galois group. }\end{cases}$$ $\endgroup$– PiquitoCommented Dec 2, 2023 at 18:07
-
$\begingroup$ Pick a random x in $\mathbb{F}_p$. In 50% of cases you have two $y$ which you can randomly choose from. What do you want to improve on that? $\endgroup$– Chris WuthrichCommented Dec 2, 2023 at 22:22
-
$\begingroup$ @ChrisWuthrich This is almost the uniform distribution, but not quite because of $2$-torsion points, or am I missing something? If you count the points (which can be done in poly time), you can account for that. But this comment is too small for a "step by step algorithm" that counts points in polynomial time. $\endgroup$– AurelCommented Dec 4, 2023 at 14:22
-
$\begingroup$ @Aurel Do you need to count for the 2-torsion points,? When hitting such an $x$, you can just decide 50/50 between taking it or not; similar for $O$. Though, my comment was trying to find out if @R Arthur has thought that far and if they wanted us to discuss this (or any other issues). From the question it is hard to understand what has been tried so far. $\endgroup$– Chris WuthrichCommented Dec 4, 2023 at 14:33
-
$\begingroup$ @ChrisWuthrich You are right, no need to count points, you can reject-sample as you propose. I agree with your comments on the actual question. $\endgroup$– AurelCommented Dec 4, 2023 at 20:58
Add a comment
|