small enhancements to generic discrete logs

[k3w1k0d3r]

Previously, the generic discrete log function wouldn't ever use Pollard's rho. From what I can tell, no generic Pohlig-Hellman implementation existed which used Pollard's rho.

Additionally, discrete log functions did not seem to properly use the custom operation arguments.

CC: @yyyyx4

Component: group theory

Keywords: discrete, logarithm, group theory, generic

Author: Julien Grijalva

Branch/Commit: 63684ec

Reviewer: Lorenz Panny

Issue created by migration from https://trac.sagemath.org/ticket/33900

[k3w1k0d3r]

Branch: u/gh-k3w1k0d3r/better_discrete_log

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e27d84e	test
2fa0275	Added Pollard's rho support to discrete_log
5048adf	discrete log functions properly handle op argument
16c5f45	undid irrelevant change

[sagetrac-git]

Commit: 16c5f45

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

abc6d2d

fixed docstring

[sagetrac-git]

Changed commit from 16c5f45 to abc6d2d

[sagetrac-git]

Changed commit from abc6d2d to 9684efd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9684efd

fixed docstring again

[yyyyx4]

comment:8

Thanks for the contribution!

One first comment: The use_rho keyword argument should be replaced by an algorithm argument (with options "bsgs"/"rho" and a reasonable default choice among these), as is standard practice throughout most of the Sage library. This makes sure the interface doesn't get awkward if someone wants to add another algorithm option later.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1888426

changed use_rho keyword to algorithm

[sagetrac-git]

Changed commit from 9684efd to 1888426

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

54bf499

fix discrete_log_generic

[sagetrac-git]

Changed commit from 1888426 to 54bf499

[yyyyx4]

comment:11

Thanks. Some more comments:

• There's a spurious whitespace change in build/bin/sage-bootstrap-python.
• Your ValueError("unkown algorithm") contains a typo ("unkown" -> "unknown").
• That same ValueError is immediately caught by the function and results in an incorrect "no discrete log" error.
• The logic here:

    mult = op if op is not None else [add, mul][operation in multiplication_names]
    power = [mul, pow][operation in multiplication_names]
    if(op is not None):
        power = lambda x, y: multiple(x, y, operation=operation, identity=identity, inverse=inverse, op=op)
    if ord is None:
        if operation in multiplication_names:
            mult = mul
            power = pow
            try:
                ord = base.multiplicative_order()
            except Exception:
                ord = base.order()
        elif operation in addition_names:
            mult = add
            power = mul

is weird. First, it should probably throw an error if operation is neither in addition_names nor in multiplication_names. Second, if operation is given but ord is not, this sets both mult and power twice (to the same value). Third, coding style: if(foo): should be if foo: in Python. Fourth, you use an if to set power, but the ternary x if y else z to set mult; this can be streamlined into a single if.

• This should probably say "in the group":

+    - ``op()`` - function of 2 arguments ``x``, ``y`` returning ``x*y`` in group

[sagetrac-git]

Changed commit from 54bf499 to f2cc977

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f2cc977

more specific bounds passed to bsgs by discrete_log

[k3w1k0d3r]

comment:13

Replying to @yyyyx4:

Thanks. Some more comments:

• There's a spurious whitespace change in build/bin/sage-bootstrap-python.
• Your ValueError("unkown algorithm") contains a typo ("unkown" -> "unknown").
• That same ValueError is immediately caught by the function and results in an incorrect "no discrete log" error.
• The logic here:

    mult = op if op is not None else [add, mul][operation in multiplication_names]
    power = [mul, pow][operation in multiplication_names]
    if(op is not None):
        power = lambda x, y: multiple(x, y, operation=operation, identity=identity, inverse=inverse, op=op)
    if ord is None:
        if operation in multiplication_names:
            mult = mul
            power = pow
            try:
                ord = base.multiplicative_order()
            except Exception:
                ord = base.order()
        elif operation in addition_names:
            mult = add
            power = mul

is weird. First, it should probably throw an error if operation is neither in addition_names nor in multiplication_names. Second, if operation is given but ord is not, this sets both mult and power twice (to the same value). Third, coding style: if(foo): should be if foo: in Python. Fourth, you use an if to set power, but the ternary x if y else z to set mult; this can be streamlined into a single if.

• This should probably say "in the group":

+    - ``op()`` - function of 2 arguments ``x``, ``y`` returning ``x*y`` in group

thanks

[sagetrac-git]

Changed commit from f2cc977 to 56526fc

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

461197a	a few adjustments
56526fc	changes to discrete_log bounds handling

[k3w1k0d3r]

comment:15

I didn't think sagemath/sagetrac-mirror@f2cc977 through very well and the tests didn't detect my mistake, I've now undone that change.

[k3w1k0d3r]

comment:16

is it looking better now?

[k3w1k0d3r]

comment:17

is there any update on this?

[yyyyx4]

comment:18

Sorry for the long silence. What's still missing are tests for the new algorithm flag: I guess you can just copy some of the existing tests and show that they also work if you pass algorithm='rho'.

Once that's done, I think this can be merged — while there are still plenty of things I would change in that file, it's certainly better than before.

[yyyyx4]

Reviewer: Lorenz Panny

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7261907

added tests for algorithm='rho'

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3d7f800

fixed order correction

[sagetrac-git]

Changed commit from 7f9cdb6 to 3d7f800

[sagetrac-git]

Changed commit from 3d7f800 to 0a648f1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0a648f1

randomly test group order instead of just base order

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

eb28739

fix silent failure issue when base == identity

[sagetrac-git]

Changed commit from 0a648f1 to eb28739

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d2a9e32

i, j initialized off by one

[sagetrac-git]

Changed commit from eb28739 to d2a9e32

[k3w1k0d3r]

comment:50

finally got the last bug I've noticed out.

[yyyyx4]

comment:51

Looks good, thank you for all the work.

Now we just need to avoid the doctest failures when lambda fails randomly. Maybe like this?

--- a/src/sage/groups/generic.py
+++ b/src/sage/groups/generic.py
@@ -851,9 +851,14 @@ def discrete_log(a, base, ord=None, bounds=None, operation='*', identity=None, i
         ....:     hi = randrange(sol+1, 2*order)
         ....:     assert lo <= sol <= hi
         ....:     kwargs['bounds'] = (lo, hi)
-        sage: res = discrete_log(*args, **kwargs)
-        sage: res == sol
-        True
+        sage: try:
+        ....:     res = discrete_log(*args, **kwargs)
+        ....: except ValueError:
+        ....:     # lambda can fail randomly
+        ....:     if kwargs['algorithm'] != 'lambda':
+        ....:         raise
+        ....: else:
+        ....:     assert res == sol

     AUTHORS:

You may also want to consider adding yourself to the list of authors for the discrete_log function.

[k3w1k0d3r]

comment:52

thanks. is there any reason to leave lambda in the random tests if we don't actually check if it worked?

[yyyyx4]

comment:53

We still check res == sol in case there is no exception. Thus, the test is not vacuous: It guarantees that if the lambda implementation returns something, then it's correct.

[sagetrac-git]

Changed commit from d2a9e32 to 63684ec

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

07682a6	made lambda test not randomly fail
63684ec	added to authors list

[k3w1k0d3r]

comment:55

thank you!

[vbraun]

Changed branch from u/gh-k3w1k0d3r/better_discrete_log to 63684ec