Submission information
Submission Number: 102
Submission ID: 166
Submission UUID: 46edd47b-dc6a-4d3f-b771-7112b2436b46
Submission URI: /form/project
Created: Tue, 07/06/2021 - 16:50
Completed: Tue, 07/06/2021 - 16:54
Changed: Tue, 12/07/2021 - 10:11
Remote IP address: 69.5.125.50
Submitted by: Christelle Vincent
Language: English
Is draft: No
Webform: Project
| Project Title | Action of Hecke operators on spaces of modular forms |
|---|---|
| Program | Northeast |
| Project Leader | Christelle Vincent |
| christelle.vincent@uvm.edu | |
| Mobile Phone | |
| Work Phone | |
| Mentor(s) | Keri Toksu |
| Student-facilitator(s) | Jesse Franklin, Tyler Bloom |
| Mentee(s) | |
| Project Description | There are various use cases in cryptography that require the use of an elliptic curve defined over a finite field of cryptographic size whose number of rational points is known: For example, some zero-knowledge interactive proofs require them, and new post-quantum cryptographic schemes require the construction of a supersingular elliptic curve whose endomorphism ring is unknown. Unfortunately, the state of the art in this field is a guess-and-check (as in, guess an elliptic curve, and then check how many points it has) algorithm whose asymptotic complexity is quartic in the size of the underlying finite field. This project is a first step towards developing a completely different algorithm which we believe will run in time linear in the size of the underlying finite field. At this time we will implement an algorithm that is closely related to the one we hope to develop, as it computes the action of Hecke operators on modular forms of level 1 (instead of the forms of general level N which we will need for the application we have in mind). This will allow us to identify the parts of the code that can be parallelized, as well the parts of the code that must be written in Python to access advanced mathematical software libraries such as SageMath, and those that can be written in Cython or C++ to increase speed. This will also allow us to set some performance benchmarks to estimate the constants in the asymptotic complexity estimate, which will help us determine if this new algorithm will be faster in the range of values we are considering for this application. |
| Project Deliverables | 1- Code that runs on the VACC computer and which interfaces with the L-functions and modular form database (lmfdb.org) to query for information that has been computed by other teams. 2- Code that computes part of the algorithm presented in Chapter 14 of “Computational aspects of modular forms and Galois representations” by Couveignes and Edixhoven; more specifically given a surjective homomorphism from the Hecke algebra to a finite field, the algorithm computes the associated Galois representation. |
| Project Deliverables | |
| Student Research Computing Facilitator Profile | |
| Mentee Research Computing Profile | |
| Student Facilitator Programming Skill Level | Can work with any level |
| Mentee Programming Skill Level | |
| Project Institution | University of Vermont |
| Project Address | |
| Anchor Institution | NE-University of Vermont |
| Preferred Start Date | 08/15/2021 |
| Start as soon as possible. | Yes |
| Project Urgency | Already behind3Start date is flexible |
| Expected Project Duration (in months) | 4 months |
| Launch Presentation | |
| Launch Presentation Date | |
| Wrap Presentation | |
| Wrap Presentation Date | |
| Project Milestones |
|
| Github Contributions | |
| Planned Portal Contributions (if any) | |
| Planned Publications (if any) | |
| What will the student learn? | |
| What will the mentee learn? | |
| What will the Cyberteam program learn from this project? | |
| HPC resources needed to complete this project? | |
| Notes | |
| What is the impact on the development of the principal discipline(s) of the project? | |
| What is the impact on other disciplines? | This project will impact the discipline of cryptography, by offering another algorithm to produce elliptic curves over finite fields that have a prescribed number of points. Since these curves have unknown endomorphism ring, these curves will allow the deployment of certain algorithms that require elliptic curves with unknown endomorphism ring, and reduce the run time of algorithms that use multiparty computations to come up with curves that are safe to the members of the computation. |
| Is there an impact physical resources that form infrastructure? | |
| Is there an impact on the development of human resources for research computing? | All of the members of the project, even beyond those funded by the VACC, benefited from our focus on producing practical code, as they learned to use GitLab and Python. |
| Is there an impact on institutional resources that form infrastructure? | |
| Is there an impact on information resources that form infrastructure? | |
| Is there an impact on technology transfer? | |
| Is there an impact on society beyond science and technology? | |
| Lessons Learned | Developing new algorithms is very different from deploying new algorithms. Both are very difficult and require time and care. In the future, I would do each step more separately, as each requires different skill sets and interests, and it was a little bit too disruptive to try and run one team that was up to date on both aspects of the project at once. |
| Overall results | We now have partial results and some code towards a solution to our problem, which we will attempt to leverage towards obtaining further funding for this project. |