discrete_log not working with multiple of base order

asked 2020-11-08 18:26:23 +0100

As title says, discrete_log not working when I put in some multiple of the base order in the order field. Specifically, take this for example:

sage: discrete_log(Mod(57, 91), Mod(8, 91), ord=4)
3

This works fine. Now, when I put in the group order for ord instead of the base order:

sage: discrete_log(Mod(57, 91), Mod(8, 91), ord=72)
ValueError: No discrete log of 57 found to base 8

I suspect that this has to do with the multiplier of that base order having common factors with the base order itself. If I try to use a multiple of the base order with some number relatively prime to the base order:

sage: discrete_log(Mod(57, 91), Mod(8, 91), ord=36)
27

Otherwise it fails:

sage: discrete_log(Mod(57, 91), Mod(8, 91), ord=8)
ValueError: No discrete log of 57 found to base 8

Unrelated note: I cherrypicked the examples to show that:

  • discrete_log only finds some exponent that satisfies, not necessarily the smallest one (and that's okay),
  • It's fine to give ord the base order multiplied with some factor from the group order, as long as that factor is relatively prime to the base order.
edit retag flag offensive close merge delete