輪読

モジュラー算術。
「a mod N」と書いたら「aをNで割った余り」を表し、
「a ≡ b (mod N)」と書いたら「Nを法としてaとbが合同」、すなわち「(a-b) mod N = 0」を表す。
モジュラー算術での冪乗を求めるとき、テキストでは
nが偶数のとき、x^y mod N = (x^(y/2))^2 mod Nで、
nが奇数のとき、x^y mod N = x (x^(y/2の切り下げ))^2 mod N
という関係式を使って計算していると説明しているように読めるが、
実はそこで説明しているアルゴリズムは
nが偶数のとき、x^y mod N = (x^(y/2) mod N)^2 mod Nで、
nが奇数のとき、x^y mod N = x (x^(y/2の切り下げ) mod N)^2 mod N
という関係式を使って計算しているので注意が必要である。
(この等式が成り立つことを示すのは簡単な演習問題になる。)
少々まぎらわしい。