PARI/GP for elliptic curve discrete logarithms (elllog) and Weil pairings (ellweilpairing)

[videlec]

PARI/GP implements discrete logarithm on elliptic curves

sage: F = GF(3^6,'a')
sage: a = F.gen()
sage: E = EllipticCurve([0,1,1,a,a])
sage: A = E.abelian_group()
sage: P = A.gen(0).element()
sage: from sage.libs.pari import pari
sage: pari.elllog(E, 400*P, P)
400

This should be benchmarked against the native sage implementation P.discrete_log(400*P). If relevant, PARI/GP should be an alternative in the function discrete_log.

This might apply to other functions as well, see PARI/GP elliptic curve reference card.

CC: @yyyyx4

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: c7626f6

Reviewer: Vincent Delecroix

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

[yyyyx4]

comment:1

Good idea!

Another example from recent experience: PARI computes (some?) pairings about 10 times faster than Sage.

[videlec]

comment:2

Discrete log also seems to be faster with PARI/GP (x3 on this example)

sage: Q = 400*P
sage: %timeit -n 100 pari.elllog(E, Q, P)
762 µs ± 83.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit -n 100 P.discrete_log(Q)
2.13 ms ± 73.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

[yyyyx4]

Commit: 208b2c0

[yyyyx4]

Author: Lorenz Panny

[yyyyx4]

comment:3

Alright, here's a branch. Its primary goal was to call elllog in .discrete_log(), but there's a little complication: PARI doesn't actually guarantee that elllog terminates when Q is not a multiple of P.
Hence, I added a Weil pairing check to ensure this before calling into PARI, and changed .weil_pairing() to use PARI as well. (The old implementation remains accessible via an optional algorithm= argument.)

Benchmarks with pairings in fields up to 128 bits and ECDLPs up to 40 bits indicate that the new code is about 15 times faster on average for those sizes (in both cases). The biggest speedups observed in my tests were about 25× for pairings and about 100× for ECDLPs. Minor slowdowns were only observed for really tiny instances, presumably due to the added conversions between PARI and Sage. We could add a case distinction there, but frankly, I think it doesn't matter.

Example:

sage: E = EllipticCurve(GF(986328349423), [49984317488,114040674816])
sage: P = E.random_point(); Q = 123451234512345*P
sage: %timeit P.discrete_log(Q)

9.5.rc0:

53.9 s ± 1.26 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

This branch:

2.14 s ± 8.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

While benchmarking, I also noticed that scalar multiplications in Sage are significantly (5×?) slower than PARI's ellmul, but changing that is a little more intricate, hence left for future work. I also refrained from touching .tate_pairing() for now.

---

New commits:

208b2c0

elliptic-curve points: use PARI for .discrete_log() and .weil_pairing()

[yyyyx4]

Branch: public/use_pari_elllog_and_ellweilpairing

[videlec]

comment:4

Nice.

Replying to @yyyyx4:

[...] but there's a little complication: PARI doesn't actually guarantee that
elllog terminates when Q is not a multiple of P. [...]

Where did you read that ? At ellog documentation they say to have a look at znlog documentation. And there it only says that the result is undefined (here I would translate as: algorithm terminates but got garbage) if Q is not a multiple of P. I thought it would be sufficient to check whether Q = nP at the end of the procedure.

[yyyyx4]

comment:5

In the znlog() documentation, near the bottom, it says:

In addition, Pollard rho is not able to handle the case where there are no solutions: it will enter an infinite loop.

However, the documentation also says that rho is only used for "large" sizes, so it seems like we could skip the check for the smaller instances if it's a problem. Overall, the cost of the pairing is negligible anyway (Miller's algorithm is O(log(n)) base field operations, ECDLP is worst-case O(sqrt(n))).

[videlec]

comment:6

Does the Weil pairing guarantees colinearity or the fact that Q is a multiple of P ? (not very familiar with EC myself)

[videlec]

comment:7

More precisely, there could be a denominator issue. The two following questions are different :
Q in ZZ P versus Q in K P (where K is the ground field).

[yyyyx4]

comment:8

You are right that "Q in ℚ·P" can be an issue, but in this case it isn't.

Modulo a bunch of identifications, the Weil pairing is "just" the determinant pairing: Our points live in a group isomorphic to G = (ℤ/n × ℤ/n, +), and the pairing is given by
G × G → k; ((a,b),(c,d)) ↦ z^(ad-bc)
where z is a fixed primitive nth root of unity in the base field k of the curve.

Thus, the pairing is 1 if and only if ad-bc ≡ 0 (mod n). The input vector (a,b) ∈ ℤ/n × ℤ/n corresponding to the point P ∈ E has full order n by construction (this is exactly how n was chosen), hence gcd(a,b,n) = 1. By Bézout we can find u,v ∈ ℤ such that au + bv ≡ 1 (mod n). Letting λ = cu + dv and using ad ≡ bc, we then get λ·(a,b) ≡ (c,d) as desired.

If we drop the assumption that one of the inputs has full order, we can indeed easily construct counterexamples: n=6, (a,b)=(2,0), (c,d)=(0,3).

[yyyyx4]

comment:9

Replying to @yyyyx4:

While benchmarking, I also noticed that scalar multiplications in Sage are significantly (5×?) slower than PARI's ellmul, but changing that is a little more intricate, hence left for future work.

This is now #33147.

[videlec]

Reviewer: Vincent Delecroix

[vbraun]

comment:11

sage -t --long --warn-long 55.6 --random-seed=123 src/sage/schemes/elliptic_curves/ell_point.py
**********************************************************************
File "src/sage/schemes/elliptic_curves/ell_point.py", line 1577, in sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.weil_pairing
Failed example:
    P.weil_pairing(Q,5)  # long time
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 694, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.weil_pairing[20]>", line 1, in <module>
        P.weil_pairing(Q,Integer(5))  # long time
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1626, in weil_pairing
        return E.base_field()(pari.ellweilpairing(E, P, Q, n))
      File "cypari2/auto_instance.pxi", line 10515, in cypari2.pari_instance.Pari_auto.ellweilpairing
      File "cypari2/handle_error.pyx", line 213, in cypari2.handle_error._pari_err_handle
    cypari2.handle_error.PariError: incorrect type in checkell over Fq (t_VEC)
**********************************************************************
File "src/sage/schemes/elliptic_curves/ell_point.py", line 1579, in sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.weil_pairing
Failed example:
    Q.weil_pairing(P,5)  # long time
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 694, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.weil_pairing[21]>", line 1, in <module>
        Q.weil_pairing(P,Integer(5))  # long time
      File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1626, in weil_pairing
        return E.base_field()(pari.ellweilpairing(E, P, Q, n))
      File "cypari2/auto_instance.pxi", line 10515, in cypari2.pari_instance.Pari_auto.ellweilpairing
      File "cypari2/handle_error.pyx", line 213, in cypari2.handle_error._pari_err_handle
    cypari2.handle_error.PariError: incorrect type in checkell over Fq (t_VEC)
**********************************************************************
1 item had failures:
   2 of  29 in sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.weil_pairing
    [809 tests, 2 failures, 5.56 s]
----------------------------------------------------------------------
sage -t --long --warn-long 55.6 --random-seed=123 src/sage/schemes/elliptic_curves/ell_point.py  # 2 doctests failed
----------------------------------------------------------------------

[sagetrac-git]

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

2329832	PARI's ellweilpairing() only works over finite fields
c79b74a	test is not really "long time" anymore, finishes in < 500ms

[sagetrac-git]

Changed commit from 208b2c0 to c79b74a

[yyyyx4]

comment:13

Thanks, good catch. PARI doesn't seem to like pairings over infinite fields.

[videlec]

comment:14

According to the patchbot (and sage documentation) Returns should be Return in the docstring of discrete_log.

[sagetrac-git]

Changed commit from c79b74a to c7626f6

[sagetrac-git]

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

57737cb	Merge tag '9.5' into public/use_pari_elllog_and_ellweilpairing
c7626f6	Returns -> Return

[vbraun]

Changed branch from public/use_pari_elllog_and_ellweilpairing to c7626f6