Add discrete logarithm for anomalous elliptic curves

[sylvainpelissier]

A fast method to solve the discrete logarithm in anomalous elliptic curves uses the p-adic logarithm as described in: https://link.springer.com/article/10.1007/s001459900052. I implemented the algorithm based on https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp/70508#70508 for EllipticCurvePoint_finite_field

Component: number theory

Keywords: p-adic discrete logarithm

Author: Sylvain Pelissier

Branch/Commit: 86ad465

Reviewer: Lorenz Panny

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

[sylvainpelissier]

Commit: f33b250

[sylvainpelissier]

Changed branch from u/sylvainpelissier/padic_elliptic_logarithm to u/gh-sylvainpelissier/padic_elliptic_logarithm

[yyyyx4]

Reviewer: Lorenz Panny

[yyyyx4]

comment:2

Thanks for writing this code, it looks very nice! A few comments:

• The test

+        if E.order() == E.base().order():

can be very expensive if the order of the curve hasn't been computed yet. (Not a very common scenario, but possible by using .set_order() on points.)
Suggestion: Replace by

n == E.base_field().cardinality()

or something like that.

• If I remember correctly, E.formal_group().log() is another way to construct the power series underlying this mapping. Perhaps we should add SEEALSO cross-references, and/or reuse that method (assuming it doesn't make things slower or otherwise worse)?

• Here

+        For anomalous curves with `#E = p`, the `padic_elliptic_logarithm`

you can use the syntax

:meth:`padic_elliptic_logarithm`

to turn the padic_elliptic_logarithm reference into a link in the HTML documentation.

• This change

-        EXAMPLES::
+        EXAMPLES:

             sage: F = GF((3,6),'a')

is incorrect; the documentation format requires a double colon before an indented block.

[sagetrac-git]

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

726112a

Corrections on padic_elliptic_logarithm based on remarks

[sagetrac-git]

Changed commit from f33b250 to 726112a

[sylvainpelissier]

comment:4

Thank you for your remarks they are helpful. I corrected everything expect the one related to E.formal_group().log(). I would need more time to test and understand if it works the same way or bring improvements.

[yyyyx4]

comment:5

Looks good.

One last thing: Much of the new code is a slightly modified version of https://crypto.stackexchange.com/a/70508, so we must give proper attribution in the docstring (e.g., in the AUTHORS or the ALGORITHM part).

[sagetrac-git]

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

5069aac

Add proper attribution

[sagetrac-git]

Changed commit from 726112a to 5069aac

[sylvainpelissier]

comment:7

Yes you are right. This should be fine now.

[yyyyx4]

comment:8

Here's an example for which this branch fails to compute .discrete_log():

sage: R.<x> = ZZ[]
sage: F.<i> = GF(787^2, modulus=x^2+1)
sage: E = EllipticCurve([268*i + 507, 42*i + 772])

You could either add an .is_prime_field() check, or (better) generalize the code to non-prime finite fields.

(By the way, you should set the ticket to "needs review" once it's ready from your perspective. I looked at this anyway because I didn't notice it was still "new", but in general you will only attract reviewers by setting the correct status.)

[sagetrac-git]

Changed commit from 5069aac to 3c0c8a7

[sagetrac-git]

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

3c0c8a7

Add primiality test

[sylvainpelissier]

comment:10

I've added the primality test. I have to figure out how to handle the non prime field case. Do you want me to open another ticket for that ?

[sagetrac-git]

Changed commit from 3c0c8a7 to 538f50e

[sagetrac-git]

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

538f50e

Rearrange checks

[yyyyx4]

comment:13

I think this is incorrect for non-anomalous curves over prime fields: In that case, the first if holds (so the elif branches are skipped), but for a non-cyclic group we do still have to run the pairing check to ensure there's a solution.

Given that the prime case is already working and useful on its own, I think the non-prime case should go into a new ticket.

[sagetrac-git]

Changed commit from 538f50e to 86ad465

[sagetrac-git]

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

86ad465

Correct check for anomalous curves

[sylvainpelissier]

comment:15

Good catch thank you. It is corrected.

[yyyyx4]

comment:16

Thanks!

[vbraun]

Changed branch from u/gh-sylvainpelissier/padic_elliptic_logarithm to 86ad465