4
$\begingroup$

I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies problems.

Well, what does Petit mean with meet-in-the-middle approach/strategy?

I've read that it's an approach that allows you to reduce the complexity of a problem with the aim of using brute force to solve it, but what does it mean in mathematical language?

Any help will be greatly appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The "meet in the middle approach", also known as "bidirectional search", is a method to find shortest paths in graphs. It was proposed by Pohl [1] and first used by Galbraith [2] to construct isogenies between elliptic curves $E$ and $E'$. One builds two trees of isogenies from both sides of $E$ and $E'$, and finds a collision between the two trees to obtain the shortest path from $E$ to $E'$.

[1] Bi-directional and heuristic search in path problems, I Pohl (1969).
[2] Constructing isogenies between elliptic curves over finite fields, S.D. Galbraith (2011).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ NB it's not obvious that this is an improvement: instead of searching the $N^2$ leaves of a single tree, we seek a coincidence between the $N+N$ leaves of two trees, which might still seem to take time $N^2$ to find. The key is that sorting can be done in time $O(N \log N)$, and once each tree's leaves are sorted we can find a match in time only $O(N)$. Likewise for other applications of this trick. Note that this requires on the order of $N$ space; sometimes there are refinements that reduce the space cost while keeping the $O(N \log N)$ timing. $\endgroup$
    – Noam D. Elkies
    Commented Feb 2, 2023 at 15:25
  • 1
    $\begingroup$ @NoamD.Elkies, if the structure can be hashed then it might be possible to eliminate the sort and get to $O(N)$ time. $\endgroup$
    – Peter Taylor
    Commented Feb 2, 2023 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .