Closed videlec closed 2 years ago
Good idea!
Another example from recent experience: PARI computes (some?) pairings about 10 times faster than Sage.
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)
Author: Lorenz Panny
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() |
Nice.
Replying to @yyyyx4:
[...] but there's a little complication: PARI doesn't actually guarantee that
elllog
terminates whenQ
is not a multiple ofP
. [...]
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.
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))
).
Does the Weil pairing guarantees colinearity or the fact that Q is a multiple of P ? (not very familiar with EC myself)
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).
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 n
th 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)
.
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.
Reviewer: Vincent Delecroix
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
----------------------------------------------------------------------
Thanks, good catch. PARI doesn't seem to like pairings over infinite fields.
According to the patchbot (and sage documentation) Returns
should be Return
in the docstring of discrete_log
.
Changed branch from public/use_pari_elllog_and_ellweilpairing to c7626f6
PARI/GP implements discrete logarithm on elliptic curves
This should be benchmarked against the native sage implementation
P.discrete_log(400*P)
. If relevant, PARI/GP should be an alternative in the functiondiscrete_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