一個單詞內的常數時間乘法逆
我正在玩一種算法，它一步一步計算 $ f(x) = x^{-1} \mod p $ 為了 $ 0 < x < p = 2^{64}-59 $ （筆記 $ p $ 是素數）。我使用Knuth 的 Vol 2 Algorithm X算法來計算反模素數，使用擴展 GCD，但我想知道是否有辦法讓它在一個詞內以恆定時間執行？
我在網上找到的產生常數時間倒數的技巧使用了蒙哥馬利乘法，因此不適合 64 位字。
我的目標是編寫一個 64 位密碼（可能不安全，肯定很慢，並且）使用反轉來混淆和擴散。
編輯：指定 $ p = 2^{64}-59 $ ，一個素數。
Edit2：指定歸因於 Knuth 的算法，並帶有指向具有屬性的頁面的連結。
你可以計算 $ f(x) = x^{\phi(p)-1} \bmod p $ 在恆定時間內，使用 $ O(\log p) $ 常數時間模乘法。如果 $ p $ 是素數，這減少到 $ f(x) = x^{p-2} \bmod p $
順便說一句：一般來說，稱其為“Knuth’s”算法並不是很有幫助；Knuth 在“電腦程式的藝術”中給出了數百種不同的算法。我假設您的意思是擴展歐幾里得算法？
這回答了特定情況下的原始問題 $ p=2^{64} $ . 它可以快速計算任何奇數 64 位整數的模逆，希望在任何支持符合 C99 或更高版本的 64 位編譯器上。如果基本運算是常數時間（這通常是乘法的一個問題）。
#include <stdint.h> // for uint64_t and uint32_t // given odd a, compute x such that a*x = 1 over 64 bits. uint64_t invmod(uint64_t a) { uint32_t x = (((a+2u)&4u)<<1)+a; // low 4 bits of inverse x = (2u-1u*a*x)*x; // low 8 bits of inverse x = (2u-1u*a*x)*x; // low 16 bits of inverse x = (2u-1u*a*x)*x; // low 32 bits of inverse return (2u-1u*a*x)*x; // 64 bits of inverse }理由： $ a\cdot x\equiv1\pmod{2^k}\implies a\cdot(2-a\cdot x)\cdot x\equiv1\pmod{2^{2\cdot k}} $
注意：（修訂後的）程式碼使用
2uand ，1u*因此所有涉及的數量都具有無符號類型。在 C 語言中，無符號量會產生明確定義的行為：結果以模數形式減少 $ 2^k $ 對於一些 $ k $ ，使得無符號類型表示整數 $ x $ 和 $ 0\le x<2^k $ .