From d40de259097c5e8d8fd35539560ca7c3d47523e7 Mon Sep 17 00:00:00 2001 From: Ryan Rueger Date: Sat, 1 Mar 2025 20:25:41 +0100 Subject: Initial Commit MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-Authored-By: Damien Robert Co-Authored-By: Frederik Vercauteren Co-Authored-By: Jonathan Komada Eriksen Co-Authored-By: Pierrick Dartois Co-Authored-By: Riccardo Invernizzi Co-Authored-By: Ryan Rueger [0.01s] Co-Authored-By: Benjamin Wesolowski Co-Authored-By: Arthur Herlédan Le Merdy Co-Authored-By: Boris Fouotsa --- theta_lib/utilities/strategy.py | 229 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 theta_lib/utilities/strategy.py (limited to 'theta_lib/utilities/strategy.py') diff --git a/theta_lib/utilities/strategy.py b/theta_lib/utilities/strategy.py new file mode 100644 index 0000000..550ef09 --- /dev/null +++ b/theta_lib/utilities/strategy.py @@ -0,0 +1,229 @@ +# ============================================================================ # +# Compute optimised strategy for 2-isogeny chains (in dimensions 2 and 4) # +# ============================================================================ # + +""" +The function optimised_strategy has been taken from: +https://github.com/FESTA-PKE/FESTA-SageMath + +Copyright (c) 2023 Andrea Basso, Luciano Maino and Giacomo Pope. + +Other functions are original work. +""" + +from sage.all import log, cached_function +import logging +logger = logging.getLogger(__name__) +#logger.setLevel("DEBUG") + +@cached_function +def optimised_strategy(n, mul_c=1): + """ + Algorithm 60: https://sike.org/files/SIDH-spec.pdf + Shown to be appropriate for (l,l)-chains in + https://ia.cr/2023/508 + + Note: the costs we consider are: + eval_c: the cost of one isogeny evaluation + mul_c: the cost of one element doubling + """ + + eval_c = 1.000 + mul_c = mul_c + + S = {1:[]} + C = {1:0 } + for i in range(2, n+1): + b, cost = min(((b, C[i-b] + C[b] + b*mul_c + (i-b)*eval_c) for b in range(1,i)), key=lambda t: t[1]) + S[i] = [b] + S[i-b] + S[b] + C[i] = cost + + return S[n] + +@cached_function +def optimised_strategy_with_first_eval(n,mul_c=1,first_eval_c=1): + r""" + Adapted from optimised_strategy when the fist isogeny evaluation is more costly. + This is well suited to gluing comptations. Computes optimal strategies with constraint + at the beginning. This takes into account the fact that doublings on the codomain of + the first isogeny are impossible (because of zero dual theta constants). + + CAUTION: When splittings are involved, do not use this function. Use + optimised_strategy_with_first_eval_and_splitting instead. + + INPUT: + - n: number of leaves of the strategy (length of the isogeny). + - mul_c: relative cost of one doubling compared to one generic 2-isogeny evaluation. + - first_eval_c: relative cost of an evaluation of the first 2-isogeny (gluing) + compared to one generic 2-isogeny evaluation. + + OUTPUT: + - S_left[n]: an optimal strategy of depth n with constraint at the beginning + represented as a sequence [s_0,...,s_{t-2}], where there is an index i for every + internal node of the strategy, where indices are ordered depth-first left-first + (as the way we move on the strategy) and s_i is the number of leaves to the right + of internal node i (see https://sike.org/files/SIDH-spec.pdf, pp. 16-17). + """ + + S_left, _, _, _ = optimised_strategies_with_first_eval(n,mul_c,first_eval_c) + + return S_left[n] + +@cached_function +def optimised_strategies_with_first_eval(n,mul_c=1,first_eval_c=1): + r""" + Adapted from optimised_strategy when the fist isogeny evaluation is more costly. + This is well suited to gluing comptations. Computes optimal strategies with constraint + at the beginning. This takes into account the fact that doublings on the codomain of + the first isogeny are impossible (because of zero dual theta constants). + + CAUTION: When splittings are involved, do not use this function. Use + optimised_strategy_with_first_eval_and_splitting instead. + + INPUT: + - n: number of leaves of the strategy (length of the isogeny). + - mul_c: relative cost of one doubling compared to one generic 2-isogeny evaluation. + - first_eval_c: relative cost of an evaluation of the first 2-isogeny (gluing) + compared to one generic 2-isogeny evaluation. + + OUTPUT: + - S_left: Optimal strategies "on the left"/with constraint at the beginning i.e. meeting the + first left edge that do not contain any left edge on the line y=sqrt(3)*(x-1). + - S_right: Optimal strategies "on the right" i.e. not meeting the fisrt left edge (no constraint). + """ + + # print(f"Strategy eval: n={n}, mul_c={mul_c}, first_eval_c={first_eval_c}") + + eval_c = 1.000 + first_eval_c = first_eval_c + mul_c = mul_c + + S_left = {1:[], 2:[1]} # Optimal strategies "on the left" i.e. meeting the first left edge + S_right = {1:[]} # Optimal strategies "on the right" i.e. not meeting the first left edge + C_left = {1:0, 2:mul_c+first_eval_c } # Cost of strategies on the left + C_right = {1:0 } # Cost of strategies on the right + for i in range(2, n+1): + # Optimisation on the right + b, cost = min(((b, C_right[i-b] + C_right[b] + b*mul_c + (i-b)*eval_c) for b in range(1,i)), key=lambda t: t[1]) + S_right[i] = [b] + S_right[i-b] + S_right[b] + C_right[i] = cost + + for i in range(3,n+1): + # Optimisation on the left (bd: + cost_k = C_middle[i-d] + C_middle[d] + d*mul_c + (i-d)*eval_c + if cost_k