Skip to content

Lighter construction of finite field elements from lists #35358

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Apr 6, 2023
Merged

Lighter construction of finite field elements from lists #35358

merged 1 commit into from
Apr 6, 2023

Conversation

remyoudompheng
Copy link
Contributor

📚 Description

When doing intensive polynomial arithmetic with the NTL implementation the constructor with lists is called a large number of times and may spend a lot of time constructing the vector_space and FreeModuleElement objects.

The very common call to vector_space(map=False) is optimized to be as cheap as possible using the already cached object.

The common case of lists of length 0 and 1 is replaced by cheaper shortcuts.

This improves performance when doing intensive polynomial computations over finite field extensions.

📝 Checklist

  • The title is concise, informative, and self-explanatory.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

@remyoudompheng
Lighter construction of finite field elements from lists
63c3ab6 
When doing intensive polynomial arithmetic with the NTL implementation
the constructor with lists is called a large number of times
and may spend a lot of time constructing the vector_space and
FreeModuleElement objects.

The very common call to vector_space(map=False) is optimized to be as cheap as
possible using the already cached object.

The common case of lists of length 0 and 1 is replaced by cheaper
shortcuts.
@remyoudompheng remyoudompheng requested a review from tscrim March 27, 2023 06:46
@remyoudompheng
Copy link
Contributor Author

Elliptic curve isogenies provide examples for a few scenarios:

  • polynomial with many zeros, most coefficients belong to the prime subfield
  • polynomial with many zeros
  • polynomial with few zeros

Benchmark before patch:

sage: p = next_prime(2**128)
sage: K = GF(p**2, 'a')
sage: E = EllipticCurve(K, [0, 1])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
1.3 s ± 4.56 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

sage: E = EllipticCurve(K, [0, K.gen()])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
2.38 s ± 6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

sage: E = EllipticCurve(K, [K.gen(), K.gen()])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
4.78 s ± 8.36 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

After patch:

sage: p = next_prime(2**128)
sage: K = GF(p**2, 'a')
sage: E = EllipticCurve(K, [0, 1])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
602 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

sage: E = EllipticCurve(K, [0, K.gen()])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
779 ms ± 4.41 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

sage: E = EllipticCurve(K, [K.gen(), K.gen()])
sage: pol = E.torsion_polynomial(97).monic()
sage: %timeit E.isogeny(pol, check=False)
1.48 s ± 13.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

tscrim
tscrim approved these changes Mar 27, 2023
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM (assuming the tests pass).

@remyoudompheng remyoudompheng mentioned this pull request Mar 27, 2023
Merged
5 tasks
@tornaria tornaria mentioned this pull request Apr 4, 2023
Merged
5 tasks
@vbraun vbraun merged commit 65f4cd2 into sagemath:develop Apr 6, 2023
vbraun pushed a commit that referenced this pull request Apr 13, 2023
7d47e1e 
gh-35370: Faster Kohel isogenies without bivariate polynomials
    
### 📚 Description

This patch accelerates computation of Kohel formulas by replacing
internal bivariate polynomials k[x,y] by a tower of polynomial rings
k[x][y].

Because the y-coordinate of isogenies are always defined by a polynomial
of y-degree 1, this is equivalent to working with a pair of univariate
polynomials, which often have efficient representations especially over
finite fields.

The public API still exposes bivariate rational functions and is not
modified.

The resulting representation is several times faster.

### 📝 Checklist

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation accordingly.

### ⌛ Dependencies

This change is self-contained but is meant to be combined with 2 other
changes:

- (to be published) faster `__call__` for NTL ZZ_pX polynomials
- #35358 : provides additional performance (independent patch)
    
URL: #35370
Reported by: Rémy Oudompheng
Reviewer(s): Lorenz Panny
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@tscrim tscrim tscrim approved these changes

Assignees
No one assigned
Labels
c: finite rings t: performance
Projects
None yet
Milestone
sage-10.0
Development

Successfully merging this pull request may close these issues.
4 participants
@remyoudompheng @tscrim @vbraun @mkoeppe