新型理想-同源翻译算法：提升效率与灵活性

### 新型理想 - 同源翻译算法：提升效率与灵活性 在数学计算领域，理想 - 同源翻译在有效德林对应计算中起着关键作用。本文将介绍一种新的算法，它在解决通用极大序中的方程以及实现理想 - 同源翻译方面展现出显著优势，尤其能提升 SQISign 密钥生成和签名的效率。 #### 通用极大序中的范数方程求解算法 为了解决通用极大序中的方程，我们引入了 SpecialEichlerNorm 算法。该算法旨在输出范数整除 $T^2$ 的元素 $\beta$，且满足 $\beta \notin Z + K$ 的约束条件。 **算法步骤如下**： ```plaintext Algorithm 3. SpecialEichlerNorm(O, K) Input: O a maximal order and K a left O-ideal of norm ℓ. Output: β ∈O ∖(Z + K) of norm dividing T 2. 1: Compute I = I(O0, O), the ideal connecting O0 to O. 2: Set L = RandomEquivalentPrimeIdeal(I), N = n(L) and compute α s.t L = Iα. 3: Compute K′ = α−1Kα 4: Compute (C : D) = EichlerModConstraint(L, 1, 1). 5: Enumerate all possible solutions of μ = FullStrongApproximation(N, C, D) until μ ̸∈Z + K′. If it fails go back to Step 2. 6: return β = αμα−1. ``` 在合理的启发式假设下，当 $T > p^{5/4}$ 时，该算法是正确的，并且以恒定概率终止。证明过程涉及对多个子算法的正确性和终止性分析，以及对输出元素 $\mu$ 满足特定条件的概率假设。 需要注意的是，使用新的 FullStrongApproximation 变体很重要，因为旧的 StrongApproximation 可能无法满足 $\mu \notin Z + K$ 的条件。此外，算法可能会在某些启发式假设不准确时失败，特别是当 RandomEquivalentPrimeIdeal(I) 的输出范数比预期大时。为解决这个问题，可以尝试增加 $T$ 的大小，但这不是最优解。也可以在某些情况下修改 FullStrongApproximation 的输入，但可能会受到 $\mu \notin Z + K$ 条件的限制。 #### 理想 - 同源翻译新算法 传统的理想 - 同源翻译算法在效率上存在瓶颈，主要是因为需要重复评估大度数的同源性，且对 $T$ 的大小和光滑性要求较高。为了克服这些问题，我们引入了 IdealToIsogenyEichler 算法。 该算法的目标是根据输入的 $O$ - 理想 $I$ 和曲线 $E$，计算 $D$ - 同源性 $\phi_I$ 的核。与传统算法不同，IdealToIsogenyEichler 只需要一个精心选择的 $End(E)$ 中的自同态来完成翻译，这个自同态由 SpecialEichlerNorm 计算得到。 **IdealToIsogenyEichler 子算法步骤如下**： ```plaintext Algorithm 4. IdealToIsogenyEichler(O, I, J, ϕJ, P) Input: I a left O-ideal of norm ℓf, an (O0, O)-ideal J of norm ℓ• and ϕJ : E0 →E the corresponding isogeny, a generator P of E[ℓf] ∩ker( ˆϕJ). Output: ϕI of degree ℓf 1: Set K = J + Oℓf. 2: Compute θ = SpecialEichlerNorm(O, K + Oℓ) of norm dividing T 2. 3: Select α ∈I s.t I = O⟨α, ℓf⟩. 4: Compute C, D s.t. α · (C + Dθ) ∈K and gcd(C, D, ℓ) = 1 using linear algebra. 5: Take any n1|T and n2|T s.t n1n2 = n(θ). Compute H1 = O⟨θ, n1⟩and H2 = O⟨θ, n2⟩. 6: Compute Li = [J]∗Hi, and ϕi = [ϕJ]∗IdealToIsogeny(Li) for i ∈{1, 2}. 7: Compute Q = ˆϕ2 ◦ϕ1(P). 8: Compute ϕI of kernel ⟨[C]P + [D]Q⟩. 9: return ϕI. ``` 在合理的启发式假设下，该子算法是正确的，并且以压倒性概率终止。其正确性基于 SpecialEichlerNorm 算法的正确性以及对 $\t