要把求階變成因數分解,選出的底數必須有有用的階。階是偶數仍不夠:若一半次冪模待分解整數等於 ,兩個最大公因數都沒有幫助。下面證明,去除簡單情況後,均勻隨機選取一個可逆元,至少以二分之一的概率避開這些障礙。這是假設每個底數都能得到精確階的經典概率結論,並非整個量子過程的成功概率。
一半次冪
定義 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 的平方根。一次量子求階測量及其後的經典重建可能只得到階的因子或不準確的候選值。重建並驗證候選數、估計得到精確階的概率與成本,都是額外步驟;要將上面的 與量子成功率相乘,必須先證明該成功率及相應條件。
練習與解答
快速檢查
(對 、 求階 、一半次冪和所得的最大公因數。)
解答 · 答案
,;最大公因數為 和 。
快速檢查
(為甚麼 、 的階雖為偶數卻失敗?)
解答 · 答案
階為 ,但 ,所以最大公因數是 和 。定理保證的是對底數而言的概率,而不是每個底數都成功。
快速檢查
(對 、,求階、一半次冪和所得的因數。)
解答 · 答案
模 的階為 ,模 的階為 ,所以 。於是 ,它模 為 ,模 為 。因此 、。