Sage has a generic discrete log implemented which works in arbitrary
abelian groups, without any claims to be usable for groups of
cryptographic size.
If you type discrete_log? you will see many examples, including
elliptic curve examples such as this one:
An additive example: elliptic curve DLOG:
sage: F=GF(37^2,'a')
sage: E=EllipticCurve(F,[1,1])
sage: F.<a>=GF(37^2,'a')
sage: E=EllipticCurve(F,[1,1])
sage: P=E(25*a + 16 , 15*a + 7 )
sage: P.order()
672
sage: Q=39*P; Q
(36*a + 32 : 5*a + 12 : 1)
sage: discrete_log(Q,P,P.order(),operation='+')
39
I just noticed that the first two lines of this doctest are redundant,
so if anyone would like a really easy case to get started with Sage
development, open a ticket to fix that!
John Cremona
On 17 November 2013 14:16, Georgi Guninski <[email protected]> wrote:
> On Sun, Nov 17, 2013 at 05:25:10AM -0800, absinthe wrote:
>> Hi everyone,
>>
>> I'd like to know if there is any implementation in Sage for inverting
>> multiplication over elliptic curves. To clarify the question as many might
>> misunderstand the problem with discrete log...
>> Let's assume that we have a curve E, but we don't know the number of points
>> of E. Moreover, for given k, P we know that P=kQ and we want to find Q. If
>> k=2 then we have the point halving problem which can be done efficiently (I
>> don't know though if there is a Sage implementation for that). Are you aware
>> of any algorithm for general k?
>>
>> Thanks
>>
>
> Have tried point.division_points(k) ?
>
> e.g:
>
> sage: E=EllipticCurve(QQ,[1,1,13,0,0]);P=E([0,0]);k=3;Q= k *
> P;pts=Q.division_points(k);pts
> [(0 : 0 : 1)]
>
> Type "P.division_points?" for help.
>
> Note that you can get more than one point.
>
> In this case over QQ P.height() might give you the correct solution,
> over GF(p) many points are discrete log IMHO.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/groups/opt_out.
