|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The supersingular isogeny problem in genus 2 and beyond | | Craig Costello
; Benjamin Smith
; | | Date: |
2 Dec 2019 | | Abstract: | Let $A/overline{mathbb{F}}_p$ and $A’/overline{mathbb{F}}_p$ be
supersingular principally polarized abelian varieties of dimension $g>1$. For
any prime $ell
e p$, we give an algorithm that finds a path $phi colon A
ightarrow A’$ in the $(ell, dots , ell)$-isogeny graph in
$widetilde{O}(p^{g-1})$ group operations on a classical computer, and
$widetilde{O}(sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum
computer. The idea is to find paths from $A$ and $A’$ to nodes that correspond
to products of lower dimensional abelian varieties, and to recurse down in
dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith)
can be invoked to connect the paths in dimension $g=1$. In the general case
where $A$ and $A’$ are any two nodes in the graph, this algorithm presents an
asymptotic improvement over all of the algorithms in the current literature. In
the special case where $A$ and $A’$ are a known and relatively small number of
steps away from each other (as is the case in higher dimensional analogues of
SIDH), it gives an asymptotic improvement over the quantum claw finding
algorithms and an asymptotic improvement over the classical van
Oorschot--Wiener algorithm. | | Source: | arXiv, 1912.0701 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER