算法2 改进的高基Montgomery模乘算法

输入: $X = ∑ i = 0 m - 1 x i ⋅ (232) i; Y = ∑ i = 0 m - 1 y i ⋅ (232) i;$

其中, $0 < X, Y < P, P < R = 2 32 · m, g c d P, 232 = 1$ .

输出: $Z = X Y R - 1 m o d P$ .

1. $Z 0 = 0;$

2. $F O R i = 0 t o L 32 - 1$

3. $c = X i Y 0$

4. $q i = Z i + c m o d 232 P' m o d 232$

5. $I F L ≤ 272$

6. $t 1 = q i P$

7. $t 2 = X i Y / 232 232 + c$

8. $E L S E$

9. $t 10 = q i (P m o d 2 L / 2)$

10. $t 11 = q i P / 2 L / 2 2 L / 2 + t 10$

11. $t 20 = X i (Y / 232 m o d 2 (L - 32) / 2)$

12. $t 21 = X i Y / 2 L / 2 + 16 2 (L - 32) / 2 + t 20 232 + c$

13. $t 1 = t 11, t 2 = t 21$

14. $E N D I F$

15. $Z i + 1 = (Z i + t 1 + t 2) / 232$

16. END FOR

17. $I F Z i + 1 ≥ P$ $T H E N Z i + 1 = Z i + 1 - P;$ $E N D I F$

18. $R E T U R N Z i + 1$