246
D. Gorodecky and T. Villa
This formula can be applied recursively producing reduced intermediate results at
every step. The coefficient 2 δ·(i−1) (mod P ) is a constant and it does not exceed
P − 1. At the first step, it holds that X i = 2 δ − 1, since Eq. (11.3) achieves the
maximum value. Then Eq. (11.3) is called recursively until the result is ≤ 2 · P .
At the end, the result is compared with P and, if needed, P is subtracted from the
result of the last step. The overall flow (reminiscent of the Fourier computation) is
represented by Algorithm.
Algorithm Modulus function computation
Input:
X = (x n , x n−1 , . . . , x 1 )
P
r = =log 2 P
k = =
n
r
length(X)—bit range of X
con(p − q : L)—concatenation (p − q) zeros as the most significant bits to L
if length(X) < k · r then
(k · r − n : X)
end if
X = (X k , X k−1 , · · · , X 1 )
X 1 = (x r , x r−1 , . . . , x 1 )
X 2 = (x 2·r , x 2·(r−1) , . . . , x r+1 )
· · ·
X i = (x i·r , x i·(r−1) , . . . , x i·(r+1) )
· · ·
X k = (x k·r , x k·(r−1) , . . . , x k·(r+1) )
S =
k
i=1
X i · (2 i·(r−1) )(modP )
S temp = S
while S temp > 2 · P do:
n temp = length(S temp )
k temp = =
ntemp
r
if length(S temp ) < k temp · r then
(k temp · r − n temp : S temp )
end if
S 1
temp = (s r , s r−1 , . . . , s 1 )
S 2
temp = (s 2·r , s 2·(r−1) , . . . , s r+1 )
· · ·
S i
temp = (s i·r , s i·(r−1) , . . . , s i·(r+1) )
· · ·
S
ktemp
temp = (s ktemp·r , s ktemp·(r−1) , . . . , s ktemp·(r+1) )
S temp =
k
i=1
S i
temp · (2 i·(r−1) )(modP )
end while
if P ≤ S temp then
S = S temp − P
else
S = S temp
end if