要把求阶变成因数分解,选出的底数必须具有有用的阶。阶是偶数仍不够:若一半次幂模待分解整数等于 ,两个最大公因数都没有帮助。下面证明,去除简单情形后,均匀随机选取一个可逆元,至少以二分之一的概率避开这些障碍。这是假设每个底数都能得到精确阶的经典概率结论,并非整个量子过程的成功概率。
一半次幂
定义 2.6.1
(阶与一半次幂)
对模 的单位 , 是满足 的最小正整数 。当 为偶数时, 的一半次幂是 。
设正奇整数 至少有两个不同的素因子, 从 均匀选取。记 为满足 的最小正整数。若 为偶数,令 。于是 ,而阶的最小性保证 。若又有 ,则
都是非平凡因子。因为 ,若其中一个最大公因数为 1,消去后会使另一个因子被 整除,与相应的排除条件矛盾;两个最大公因数也都不等于 。
随机底数定理
定理 2.6.2
(有用的阶出现的概率至少为二分之一)
若正奇整数 至少有两个不同素因子,则均匀随机可逆元 的阶 为偶数且满足 的概率至少为 。
证明
(比较局部阶中 2 的幂次)
分解 ,其中 , 是互不相同的奇素数。中国剩余定理把模 的均匀随机可逆元对应到各模 上独立均匀的可逆元 。令 , 为 中 2 的指数。全局阶为 。
若所有 ,则 为奇数。否则记 。当 时, 整除 ,故 。当 时, 的阶为 2。奇素数幂模下 只有 和 两根:奇素数 不能同时整除 和 ;由于 整除它们的乘积, 必整除其中被 整除的那个因子。因此这一分量的值是 。于是过程失败恰好发生在所有 相等时:全为零使阶为奇数;相等且为正使每个分量的 都为 。若它们不全相等, 同时有 和 分量,最大公因数便能分解 。
剩下要估计相等的概率。奇素数幂模下的可逆元群是循环群。若其阶为 ,其中 为奇数、,那么元素阶的 2 进指数为 的比例: 时是 , 时是 。每一项至多为 。这是对循环群的 2 主要分量中各阶元素计数的结果;奇数阶分量不影响 。
独立性给出
最后的和是 全相等的概率; 时它等于 1。因此有用事件的概率至少为 。
证明透视
各项假设在哪里用到
证明依靠三项假设。 在单位群上均匀分布,使中国剩余定理能把各局部分量变成相互独立,最后估计中的乘积只来自这一点。素数为奇数,使每个局部单位群是偶数阶循环群,恰有一个二阶元素,即 ;所以 最大的分量给出 ,其余分量给出 。条件 用在最后一行:它提供因子 ,乘上一个不超过一的概率。最不显然的一步是改写:过程恰好在所有 相等时失败,这把关于 的问题变成关于独立局部阶的 2-adic 赋值的问题。对 ,这个改写仍然成立,但界不成立,因为单个 自然等于自身。
例题 2.6.3
(不同的局部阶分解 21)
取 、。模 3 的阶为 2,模 7 的阶为 3,因此 ,。局部符号分别是 和 ,故 ,。相反, 的阶为 2,给出 ,只能得到 1 和 21。
例题 2.6.4
(数一数模 15 的全部单位)
模 共有 个单位:,阶依次为 。底数 的阶是奇数,底数 的一半次幂为 。对 ,一半次幂依次为 ,都不是 ,所以这六个底数都能分解 。有用底数的比例为 。
例题 2.6.5
(相等的二进赋值)
取 、。模 时 的阶为 ,模 时 的阶为 ,所以 。 的两个分量都是 ,因此 ,过程失败,与判据的预测一致。
常见错误
(偶数阶并不足够)
阶 为偶数并不表示 有用:若 ,两个最大公因数都是平凡的。对 、,阶为 ,但 ,所以 、。
反例模式
奇素数幂没有有用的底数
一个诱人的说法是:对每个奇数 ,二分之一的界都成立。取 ,单位为 ,阶依次为 。底数 的阶为奇数。对 ,一半次幂为 、、,模 都同余于 。所以没有任何底数能分解 ,有用底数的比例是 ,而不是至少 。至少有两个不同素因子的假设不能去掉,这也是素数幂要另行处理的原因。
这个界计入了什么
实际操作可以先从 中均匀取整数并计算它与 的最大公因数。若该因数非平凡,就已经完成分解;在最大公因数为 1 的条件下,取到的数在可逆元中均匀分布,符合上面的假设。偶数和素数幂要另行处理;定理排除奇素数幂,因为那里未必存在非平凡的 1 的平方根。一次量子求阶测量及其后的经典重建可能只得到阶的因子或不准确的候选值。重建并验证候选数、估计得到精确阶的概率与成本,都是额外步骤;要将上面的 与量子成功率相乘,必须先证明该成功率及相应条件。
练习与解答
快速检查
(对 、 求阶 、一半次幂和所得的最大公因数。)
解答 · 答案
,;最大公因数为 和 。
快速检查
(为什么 、 的阶虽为偶数却失败?)
解答 · 答案
阶为 ,但 ,所以最大公因数是 和 。定理保证的是对底数而言的概率,而不是每个底数都成功。
快速检查
(对 、,求阶、一半次幂和所得的因数。)
解答 · 答案
模 的阶为 ,模 的阶为 ,所以 。于是 ,它模 为 ,模 为 。因此 、。