15.4.2 べき剰余

べき剰余は，2^k項のスライディングウィンドウアルゴリズム(“Handbook of Applied Cryptography” algorithm 14.85 (see References)参照）で実装されています。kは指数の大きさに従って決めます。大きな指数に対しては大きなkを使用して，2乗を求めるための平均乗算回数を最小化します。

剰余乗算と剰余平方は，単純除算か，Montgomeryアルゴリズム(see References)によるREDCによって求めます。REDCの方は多少高速にはなりますが，本質的にはN回の単一リム除算を，完全剰余計算(see Exact Remainder)に似たやり方で減らしています。