242
D. Gorodecky and T. Villa
11.3.2 Approach Based on the Periodic Property of Powers
of Two
Another approach is based on using the periodic property of residues of 2 k (mod P )
[13, 14, 18]. Denoting 2 j ≡ 1(mod P ), it is known that 2 α·j +i ≡ 2 i (mod P ), if
value α is the period of the modulus P . It means that an n-bit input can be split
into j α-bit vectors starting from the least significant bits. The value “j ” is “order”
and can be P − 1 or less. Considering the example from [13], let P = 19 and
X = 89887166171 10 = 0001010011101101101100010100111011011011 2 , then
α = 18. Thus, the three (as α = 18) 18-bit vectors (adding 14 bits as the most
significant to the third vector) can be added to obtain:
00 0000 0000 0000 0001
01 0011 1011 0110 1100
01 0100 1110 1101 1011
10 1000 1010 0100 1000
This corresponds to 166,472. The residue of this 18-bit number can be obtained
next by adding the residues of various powers of 2(mod 19). In short, the
periodic property of 2 k mod m has been used to simplify the computation. Further
simplification is possible for moduli satisfying the property 2 (P −1)/2 (mod P ).
Considering P = 19, we observe that 2 9 = −1(mod 19), 2 10 = −2(mod 19), . . . ,
2 17 = 10(mod 19), 2 18 = 1(mod 19) and 2 19 = 2(mod 19), etc. [13]. Thus, the
residues in the upper half of a period are opposite in sign to those in the lower half of
the period. Denoting the successive words of half period length as W 0 , W 1 , . . . , W α ,
where α is odd, we need to estimate
(α−1)/2
i=0
W 2i −
(α−1)/2
i=0
W 2i+1
[13]. For the
same example we first divide the given word into 9-bit fields starting from the least
significant bits as follows:
W 4 = 0001
W 3 = 0 1001 1101
W 2 = 1 0110 1100
W 1 = 0 1010 0111
W 0 = 0 1101 1011
Then, adding W 0 , W 2 , W 4 we get S e = 10 0100 1000 and adding W 1 , W 3 we get
W 0 = 1 0100 0100. Subtracting S o from S 1 we have S = 0001 0000 0100. The word
lengths of S o and S e can be more than j/2 bits depending on the number of j/2-bit
fields in the given binary number. The residue of the resulting word can be found
D. Gorodecky and T. Villa
11.3.2 Approach Based on the Periodic Property of Powers
of Two
Another approach is based on using the periodic property of residues of 2 k (mod P )
[13, 14, 18]. Denoting 2 j ≡ 1(mod P ), it is known that 2 α·j +i ≡ 2 i (mod P ), if
value α is the period of the modulus P . It means that an n-bit input can be split
into j α-bit vectors starting from the least significant bits. The value “j ” is “order”
and can be P − 1 or less. Considering the example from [13], let P = 19 and
X = 89887166171 10 = 0001010011101101101100010100111011011011 2 , then
α = 18. Thus, the three (as α = 18) 18-bit vectors (adding 14 bits as the most
significant to the third vector) can be added to obtain:
00 0000 0000 0000 0001
01 0011 1011 0110 1100
01 0100 1110 1101 1011
10 1000 1010 0100 1000
This corresponds to 166,472. The residue of this 18-bit number can be obtained
next by adding the residues of various powers of 2(mod 19). In short, the
periodic property of 2 k mod m has been used to simplify the computation. Further
simplification is possible for moduli satisfying the property 2 (P −1)/2 (mod P ).
Considering P = 19, we observe that 2 9 = −1(mod 19), 2 10 = −2(mod 19), . . . ,
2 17 = 10(mod 19), 2 18 = 1(mod 19) and 2 19 = 2(mod 19), etc. [13]. Thus, the
residues in the upper half of a period are opposite in sign to those in the lower half of
the period. Denoting the successive words of half period length as W 0 , W 1 , . . . , W α ,
where α is odd, we need to estimate
(α−1)/2
i=0
W 2i −
(α−1)/2
i=0
W 2i+1
[13]. For the
same example we first divide the given word into 9-bit fields starting from the least
significant bits as follows:
W 4 = 0001
W 3 = 0 1001 1101
W 2 = 1 0110 1100
W 1 = 0 1010 0111
W 0 = 0 1101 1011
Then, adding W 0 , W 2 , W 4 we get S e = 10 0100 1000 and adding W 1 , W 3 we get
W 0 = 1 0100 0100. Subtracting S o from S 1 we have S = 0001 0000 0100. The word
lengths of S o and S e can be more than j/2 bits depending on the number of j/2-bit
fields in the given binary number. The residue of the resulting word can be found