An Algorithm for Efficient Detection of (N, N)-Splittings and Its Application to the Isogeny Problem in Dimension 2

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N, N)-split for each integer \(N \le 11\) . Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor of 25; when the underlying prime is 200 bits, the attack is sped up by a factor of 42; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of 160.