discrete_log not working with multiple of base order
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.