inconsistent API for .log() method in finite fields
#38350
Milestone
Comments
5 tasks
yyyyx4
added a commit
to yyyyx4/sage
that referenced
this issue
Jul 17, 2024
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Jul 20, 2024
…inite field elements
<!-- ^ Please provide a concise and informative title. -->
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
<!-- v Why is this change required? What problem does it solve? -->
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->
Fixes sagemath#38350 by adding `order=` and `check=` arguments to the `.log()`
method of finite field elements, under all implementations.
- `element_pari_ffelt.pyx`: done by @yyyyx4 in sagemath#37329.
- `element_ntl_gf2e.pyx`: if provided, does not compute `base_order`.
- `element_givaro.pyx`: if provided, passes `order` to the underlying
`discrete_log` call.
- `integer_mod.pyx`: the argument is discarded (unless `check=True`, in
which case the order is checked).
### 📝 Checklist
<!-- Put an `x` in all the boxes that apply. -->
- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.
### ⌛ Dependencies
<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
URL: sagemath#38359
Reported by: Justin Carel
Reviewer(s): Lorenz Panny
yyyyx4
added a commit
to yyyyx4/sage
that referenced
this issue
Aug 1, 2024
yyyyx4
added a commit
to yyyyx4/sage
that referenced
this issue
Aug 1, 2024
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Aug 9, 2024
…tic-curve points
The points on an elliptic curve over a finite field form a group of rank
up to $2$. In this patch we add support for passing two base points
instead of just one to the `.log()` method, which will decompose the
given point as a linear combination of the given points. This
functionality is already available via the `.abelian_group()` method of
the elliptic curve, but the latter is much slower since it relies only
on generic-group algorithms and does not exploit the Weil pairing:
```
sage: F = GF((5, 60), 'a')
sage: E = EllipticCurve(F, [1, 1])
sage: A = E.abelian_group()
sage: P, Q = E.gens()[::-1]
sage: T = randrange(P.order()) * P + randrange(Q.order()) * Q
sage: %time A.discrete_log(T, [P,Q])
CPU times: user 47.4 s, sys: 74 ms, total: 47.5 s
Wall time: 47.6 s
(2474, 185989333112663415489036252299763200191)
sage: %time T.log([P, Q])
CPU times: user 1.43 s, sys: 3.34 ms, total: 1.44 s
Wall time: 1.44 s
(2474, 185989333112663415489036252299763200191)
```
### ⌛ Dependencies
- sagemath#38350
URL: sagemath#38347
Reported by: Lorenz Panny
Reviewer(s): Giacomo Pope, Lorenz Panny
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
After #37329, the
.log()method takes an optionalorder=argument for some implementations of finite-field elements, and throws exceptions for some others when a third argument (in addition toselfand the base element) is passed.This inconsistency is annoying: All implementations of this method should accept the
order=argument and either do something useful with it or discard it silently but gracefully.The text was updated successfully, but these errors were encountered: