模反元素計算機

整數 a 在模 m 下的乘法反元素是一個整數 x，使 a 與 x 的乘積除以 m 後餘數為 1。用同餘的語言表示，即 a 乘 x 與 1 模 m 同餘。本計算機透過擴展歐幾里得算法求出最小非負反元素，並顯示乘法驗證。模數必須是大於一的整數。 若且唯若 a 與 m 互質，也就是最大公因數為 1，反元素才存在。若它們有更大的公因數，任何含 a 的乘積在模 m 下仍可被該因數整除，不可能得到餘數 1。例如，6 在模 15 下沒有反元素，因為最大公因數為 3。相較之下，3 在模 11 下的反元素是 4，因為 3 乘 4 等於 12，除以 11 後餘數為 1。 擴展歐幾里得算法不只計算最大公因數，也能找出係數 x 與 y，使 ax 加 my 等於最大公因數。當該公因數為 1 時，將 x 對 m 取模就能得到模反元素。若 x 是負數，加上足夠多個 m，便可將它移到零至 m 減一的標準範圍，而不改變其同餘類。 模反元素在模運算中取代除法。不能直接對剩餘類使用一般除法，因為不同整數可能代表同一個餘數。在模 m 下除以 a，表示乘以 a 的反元素，前提是該反元素存在。這個技巧是解一次同餘式、化簡模分式、應用中國剩餘定理，以及推導許多數論算法的核心。 密碼學廣泛使用模反元素。RSA 金鑰生成會對與歐拉函數相關的值求指數的反元素；橢圓曲線計算在有限體上求點運算公式時也使用反元素。編碼理論、檢查碼、偽隨機數產生器與電腦代數同樣仰賴有效率的反元素計算。實際密碼學實作採用精心設計的大整數與固定時間運算，而非瀏覽器的一般數值運算，但底層數論原理相同。 反元素是在模 m 的意義下唯一，不是作為一般整數唯一。如果 4 是 3 在模 11 下的反元素，那麼 15、負 7，以及所有與 4 相差 11 整數倍的數，都代表同一個反元素剩餘類。計算機顯示 4，因為最小非負代表元最方便比較與重複使用。 驗證結果時，將原整數乘以顯示的反元素，再除以模數，確認餘數是否為 1。負數輸入也適用相同規則，因為餘數總能正規化到標準範圍。若工具顯示反元素不存在，可另外計算最大公因數；任何大於 1 的值都能證明其無法成立。