Previous: , Up: Powering Algorithms   [Index]


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)に似たやり方で減らしています。