Computing discrete logs in polynomial rings modulo another polynomial over non-prime-power

[Bill Cox]

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

Thanks,

Bill

[Simon King]

Hi Bill,

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

[John Cremona]

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 sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Simon King]

Hi John,

On 2017-04-09, John Cremona <john.c...@gmail.com> wrote:
> Simon is right

I am not so sure. It somehow seems to me that the OP's question is about polynomial rings.

Yes, he uses finite fields in his example. But it seems that he wants to work with a quotient
ring of the polynomial ring over some base ring, modulo an irreducible polynomial. If
the base ring is a field, he can indeed work over the finite field that is given as an
extension of the base ring by the irreducible polynomial.

But what could he do if the base ring is not a field?

Best regards,
Simon