44、确定性素性测试与相关数学知识

确定性素性测试与相关数学知识

1. 确定性素性测试算法

1.1 AKS算法概述

AKS算法是一种确定性的素性测试算法。在该算法中，有一些关键的参数和假设对算法的分析和性能起着重要作用。例如，设 (r) 是算法第 2 步所确定的值，其与输入数 (n) 的长度 (len(n)) 存在一定的关系。根据假设 (A4)，([n]_r) 在 (\mathbb{Z}^*_r) 中的乘法阶大于 (4 len(n)^2)；根据假设 (A5)，有 (\ell > 2 len(n)\lfloor t^{1/2}\rfloor)。

1.2 AKS算法复杂度分析

• 一般情况：如果使用整数和多项式算术的快速算法，该算法的运行时间为 (O(r^{1.5 + o(1)} len(n)^{3 + o(1)}))，其中 (r) 是算法第 2 步确定的值。
• 不同分析下的复杂度：
  • 通过分析可得 (r = O(len(n)^5))，此时算法运行时间为 (O(len(n)^{10.5 + o(1)}))。
  • 利用 Fouvry 的结果，可证明 (r = O(len(n)^3))，算法运行时间为 (O(len(n)^{7.5 + o(1)}))。
  • 如果关于 Sophie Germain 素数密度的猜想 5.26 成立，那么 (r = O(len(n)^2))（可通过练习 22.1 证明），算法运行时间将为 (O(len(n)^{6 + o(1)}))。