Modulo Multiplication and Modulo Squaring
In this chapter, algorithms and implementations for modulo multiplication for general moduli as well powers of two related moduli are considered. The design of squarers also is considered in detail in view of their extensive application in cryptography an
- PDF / 1,464,391 Bytes
- 41 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 202 Views
Modulo Multiplication and Modulo Squaring
In this chapter, algorithms and implementations for modulo multiplication for general moduli as well powers of two related moduli are considered. The design of squarers also is considered in detail in view of their extensive application in cryptography and signal processing. Designs using conventional number representation as well as diminished-1 representation are described. Further, designs which can be shared among various moduli are also explored with a view to reduce area.
4.1
Modulo Multipliers for General Moduli
The residue number multiplication for general moduli (i.e. moduli not of the form (2k a)) can be carried out by several methods: using index calculus, using sub-modular decomposition, using auto-scale multipliers and based on quartersquare multiplication. Soderstrand and Vernia [1] have suggested modulo multipliers based on index calculus. Here, the residues are expressed as exponents of a chosen base modulo m. The indices corresponding to the inputs for a chosen base are read from the LUTs (look-up tables) and added mod (m 1) and then using another LUT, the actual product mod m can be obtained. As an illustration, consider m ¼ 11. Choosing base 2, since 28 mod 11 ¼ 3, and 24 mod 11 ¼ 5, corresponding to the inputs 3 and 5, the indices are 8 and 4, respectively. We wish to find (3 5) mod11. Thus, we have the index corresponding to the product as (8 + 4) mod 10 ¼ 2. This corresponds to 22mod11 ¼ 4 which is the desired answer. Note that the multiplication modulo m is isomorphic to modulo (m 1) addition of the indices. Note further that zero detection logic is required if the input is zero since no index exists. Jullien [2] has suggested first using sub-modular decomposition for index calculus-based multipliers mod m. This involves three stages (a) sub-modular © Springer International Publishing Switzerland 2016 P.V. Ananda Mohan, Residue Number Systems, DOI 10.1007/978-3-319-41385-3_4
39
40
4 Modulo Multiplication and Modulo Squaring
reconstruction (b) modulo index addition and (c) reconstruction of desired result. The choice of sub-moduli m1 and m2 such that m1m2 > 2 m has been suggested. As an illustration, for m ¼ 19, m1 ¼ 6 and m2 ¼ 7 can be chosen. Considering multiplication of X ¼ 12 and Y ¼ 17, and base 2, for modulus m ¼ 19, the indices corresponding to X and Y can be seen to be 15 and 10 which in residue form are (3, 1) and (4, 3) corresponding to (m1, m2). Adding the indices corresponding to the product XY, we obtain the indices as (1, 4). Using CRT (which will be introduced later in Chapter 5), the decoded word corresponding to moduli {6, 7} can be shown to be 25 which mod 18 is 7. Thus, the final result can be obtained as 14 since 27 mod 19 ¼ 14. Note that for input zero since index does not exist, the value 7 is used since 7 will never appear as a valid sub-modular result due to the fact that sub-moduli are less than 7. Jullien’s approach needs large ROM which can be reduced by using sub-modular decomposition due to Radhakrishnan a
Data Loading...
