Timeline for Select random point on elliptic curve
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 4, 2023 at 20:58 | comment | added | Aurel | @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. | |
| Dec 4, 2023 at 14:33 | comment | added | Chris Wuthrich | @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. | |
| Dec 4, 2023 at 14:22 | comment | added | Aurel | @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. | |
| Dec 2, 2023 at 22:22 | comment | added | Chris Wuthrich | 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? | |
| Dec 2, 2023 at 18:07 | comment | added | Piquito | 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}$$ | |
| S Dec 2, 2023 at 15:49 | review | First questions | |||
| Dec 2, 2023 at 15:53 | |||||
| S Dec 2, 2023 at 15:49 | history | asked | R Artur | CC BY-SA 4.0 |