ALOHA JESSIE

公開金鑰密碼系統各類演算法 （RAS）

擴充歐基里得演算法

已知：T，N
求   ：X滿足X×T mod N=1
Step1：A ← N
            B ← T
            X^{`</sup> ← 0
            X ← 1
Step2：Q = floor（A ÷ B）
             R = A mod B
Step3：If R ≠ 0, then goto step4
            If X Step4：A ← B
             B ← R
             X<sup>`} ← X
             X ← X`- Q ←X
                          Goto Step2

Ex：計算D滿足D×5 mod 96 = 1
Ans： 
 A         B         X`        X         Q          R
-------------------------------------------------
96        5          0          1         19          1   
 5         1           1        -19         5          0