On 9 April 2017 at 15:20, Simon King <[email protected]> wrote:
> Hi Bill,
>
> On 2017-04-08, 'Bill Cox' via sage-support <[email protected]>
> wrote:
>> I want to test finding the discrete log in the circle group over Z/Zm --
>> discrete logs of g^a mod m, where g is a complex number and m is composite.
>> Can Sage do this for large composite m, say on the order of 2^128 or more,
>> when m is smooth, containing no prime factors larger than say 1 billion?
>>
>> I can get the discrete log in the circle group for prime powers like this:
>>
>> sage: F.<a> = FiniteField(23^2, modulus=x^2 + 1)
>> sage: F.<a> = FiniteField(23^2, modulus=x^2 + 1)
>> sage: aliceSecret = (1 + a)^13
>> sage: sage: aliceSecret.log(1 + a)
>> 13
>
> Maybe I misunderstand your problem, but can't you simply do exactly the same
> thing with a quotient ring instead of a finite field?
>
> sage: m = 120011^2*12000239*5150237*7200233^2
> sage: m
> 46147940098802341021228029866464641067
> sage: R = Integers(m)
> sage: aliceSecret = R(2)^13
> sage: aliceSecret.log(2)
> 13
> sage: aliceSecret = R(19)^11231
> sage: aliceSecret.log(19)
> 11231
>
> Best regards,
> Simon
Simon is right Note that you can see what method is used via
aliceSecret?? which says
"If the modulus is prime and b is a generator, this calls Pari's ``znlog``
function, which is rather fast. If not, it falls back on the generic
discrete log implementation in
:meth:`sage.groups.generic.discrete_log`."
so you should not expect this to be fast, and maybe not even possible,
for large m.
>
> --
> 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 https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.
--
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 https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
