Timeline for Is there an algorithm to find a linear dependence between points on elliptic curves?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 20, 2015 at 14:40 | comment | added | joro | Answered. If the group order is prime, they can't be independent. They can be independent if the "generators" are not unique, in which case try all generators. Gave reference. | |
| Nov 20, 2015 at 14:36 | answer | added | joro | timeline score: 0 | |
| Nov 20, 2015 at 14:17 | comment | added | somayeh didari | OK! Finally, I get the point. In your example $P_1$ and $P_2$ are depended. But what will happen in the independent points? I think In these cases, solving DLP does not solve the problem. Is it true? | |
| S Nov 20, 2015 at 13:58 | history | suggested | Tadashi |
Added relevant tag
|
|
| Nov 20, 2015 at 13:51 | comment | added | joro | Yes, you can solve ECDLP this way. And if you can solve it, you can solve your problem too. | |
| Nov 20, 2015 at 13:50 | review | Suggested edits | |||
| S Nov 20, 2015 at 13:58 | |||||
| Nov 20, 2015 at 13:47 | history | edited | somayeh didari | CC BY-SA 3.0 |
edited body
|
| Nov 20, 2015 at 13:46 | comment | added | somayeh didari | You are right Rene, In my example the curve is defined over $\mathbb{F}_p$. I should correct it, thank you. | |
| Nov 20, 2015 at 13:45 | comment | added | somayeh didari | Ok I think I get your point Joro! You mean if I can find such relation, I can solve ECDLP. is is true? | |
| Nov 20, 2015 at 13:42 | comment | added | R.P. | Why does $\tau(Q)$ lie on $E$? You either want $E$ to be defined over $\mathbb{F}_p$ or $\tau$ to be the $q$-th power Frobenius. | |
| Nov 20, 2015 at 13:35 | comment | added | joro | Suppose given $P,Q$, you want to solve DL $Q=x P$. Give three points $P_1=2P,P_2=10P,P_3=100P$. If you can solve $Q=a_1 P_1 + a_2 P_2 + a_3 P_3$, then $Q= (2a_1+10 a_2 + 100 a_3)P$ modulo the order. | |
| Nov 20, 2015 at 13:31 | comment | added | somayeh didari | Sorry, but I can't understand. In my example $P$ and $\tau(P)$ are independent. Could you explain for me, please? | |
| Nov 20, 2015 at 13:15 | comment | added | joro | If you choose known multiples of $P$, $P_i$, won't this be exactly the discrete logarithm for $Q$ unknown multiple of $P$? | |
| Nov 20, 2015 at 13:08 | history | asked | somayeh didari | CC BY-SA 3.0 |