The modular inverse of a number refers to the modular multiplicative inverse. For any integer a such that (a, p) = 1 there exists another integer b such that ab≡ 1 (mod p). The integer b is called the multiplicative inverse of a which is denoted as b = a−1. Modular inversion is a well-defined operation for any finitering or field, not just for rings and fields of integers. However, the former will be the matter of discussion.
The simplest approach is to compute the algebraic inverse of the input; that is, to compute b = aΦ(p)−1. If Φ(p) is the order of the multiplicative subgroup modulo p, then b must be the multiplicative inverse of a-the proof of which is trivial.
(9.11)
However, as simple as this approach may be it has two serious flaws. It requires that the value of F(p) be known, which if p is composite requires all of the prime factors. This approach also is very slow as the size of p grows.
A simpler approach is based on the observation that solving for the multiplicative inverse is equivalent to solving the linear Diophantine3equation.
Where a, b, p, and q are all integers. If such a pair of integers 〈 b, q〉 exists, b is the multiplicative inverse of a modulo p. The extended Euclidean algorithm (Knuth [1, pp. 342]) can be used to solve such equations provided (a, p) = 1. However, instead of using that algorithm directly, a variant known as the binary Extended Euclidean algorithm will be used in its place. The binary approach is very similar to the binary greatest common divisor algorithm, except it will produce a full solution to the Diophantine equation.
9.4.1 General Case
Algorithm mp_invmod. This algorithm computes the modular multiplicative inverse of an integer a modulo an integer b. It is a variation of the extended binary Euclidean algorithm from HAC [2, pp. 608], and it has been modified to only compute the modular inverse and not a complete Diophantine solution (Figure 9.7).
Figure 9.7. Algorithm mp_invmod
If b≤ 0, the modulus is invalid and MP_VAL is returned. Similarly if both a and b are even, there cannot be a multiplicative inverse for a and the error is reported.
The astute reader will observe that steps 7 through 9) are very similar to the binary greatest common divisor algorithm mp_gcd. In this case, the other variables to the Diophantine equation are solved. The algorithm terminates when u = 0, in which case the solution is
(9.13)
If v, the greatest common divisor of a and b, is not equal to one, then the algorithm will report an error as no inverse exists. Otherwise, C is the modular inverse of a. The actual value of C is congruent to, but not necessarily equal to, the ideal modular inverse, which should lie within 1 = a−1< b. Steps 12 and 13 adjust the inverse until it is in range. If the original input a is within 0< a< p, then only a couple of additions or subtractions will be required to adjust the inverse.
Odd Moduli
When the modulus b is odd the variables A and C are fixed and are not required to compute the inverse. In particular, by attempting to solve the Diophantine Cb + Da = 1, only B and D are required to find the inverse of a.
The algorithm fast_mp_invmod is a direct adaptation of algorithm mp_invmod with all steps involving either A or C removed. This optimization will halve the time required to compute the modular inverse.
Pramod Pandya , in Cyber Security and IT Infrastructure Protection, 2014
GF(23) is a Finite Field
We know that GF(23) is an Abelian group because the operation of polynomial addition satisfies all of the requirements on a group operator and because polynomial addition is commutative. GF(23) is also a commutative ring because polynomial multiplication is a distributive over polynomial addition. GF(23) is a finite field because it is a finite set and because it contains a unique multiplicative inverse for every nonzero element.
GF(2n) is a finite field for every n. To find all the polynomials in GF(2n), we need an irreducible polynomial of degree n. In general, GF(pn) is a finite field for any prime p. The elements of GF(pn) are polynomials over GF(p) (which is the same as the set of residues Zp). Next we show how the multiplicative inverse of a polynomial is calculated using the Extended Euclidean Algorithm:
Multiplicative inverse of (x2+x+1) in F2[x]/(x4+x+1) is (x2+x)
(x2+x) (x2+x+1)=1 mod(x4+x+1)
Multiplicative inverse of (x6+x+1) in F2[x]/(x8+x4+x3+x+1) is (x6+x5+x2+x+1)
(x6+x+1) (x6+x5+x2+x+1)=1 mod (x8+x4+x3+x+1) [1][2]
Richard Hamming , in Classical and Quantum Information, 2012
Proof.
To prove that the condition is necessary, let us assume that p is prime. First, we observe that, Zp, has a finite number of elements, 0,1,2,…, (p – 1). Then we verify all the properties or axioms of a field. Here, we only show that given, 0 < a < p, the multiplicative inverse, a−1 exists. The gcd(p, a) = 1 because p is prime; then according to Euclid's algorithm, there exist integers, s and t, such that s · p + 1 · a = 1. But for all integers, s, we have s • p ≡ 0 mod p; this implies that t · a = 1 mod p or t = a−1 mod p. Thus, if p is prime, then ℤp is a finite field.
We start with the observation that if p is not a prime, then it is a product of two terms, p = a · b, with a, b = 0 mod p. To prove that the condition is sufficient, we have to show that b has no multiplicative inverse in ℤp. In other words, we must show that there is no c, such that b = c−1 or b · c ≡ 1 mod p. If such c exists, then
But, a ≡ 0 mod p contradicts the assumption that a ≠ 0 mod p.
Cheryl B. Schrader , in The Electrical Engineering Handbook, 2005
1.2 Vector Spaces Over Fields and Modules Over Rings
It is assumed that the reader already has some knowledge and experience with vector spaces and fields. What may not be as readily apparent is that the reader, subsequently, also has experience with modules and rings. This section briefly describes the essence of these ideas in a mathematical sense.
Real numbers, complex numbers, and binary numbers all are fields. Specifically a field F is a nonempty set F and two binary operations, addition (+) and multiplication, that together satisfy the following properties for all a, b, c ∈ F:
1.
Associativity: (a + b) + c = a + (b + c); (ab)c = a(bc).
2.
Commutativity:a + b = b + a; ab = ba.
3.
Distributivity:a(b + c) = (ab) + (ac).
4.
Additive identity:
.
5.
Multiplicative identity:
.
6.
Additive inverse: For every
. [Notation note: b = − a].
7.
Multiplicative inverse: For every nonzero,
.
[Notation note: b = a−1].
It is commonly known with real numbers that multiplication distributes over addition, and both additive and multiplicative inverses exist. In the case where a multiplicative inverse does not exist, but properties 1 through 6 hold (such as with integers), then the set does not form a field but is categorized as a commutative ring. If property 2 also does not hold, then the correct terminology is a ring.
To speak of an additive group, a single operation is used (addition) along with a nonempty set G, satisfying additive properties 1, 4, and 6. If in addition the operation is commutative (as described in property 2), then the additive group is abelian.
To discuss an F-vector spaceV, one simply requires a nonempty set V and a field F that together with binary operations + : V × V → V and * : F × V → V satisfy the following axioms for all elements v, w ∈ V and a, b ∈ F:
1.
V and + form an additive abelian group.
2.
a * (v + w) = (a * v) + (a * w).
3.
(a + b) * v = (a * v) + (b * v).
4.
(ab) * v = a * (b * v).
5.
1 * v = v.
Vectors are elements of V, and scalars are elements of F. Often, one uses the terminology vector spaceVover the fieldF. What form vectors may take will be examined more closely in Section 1.3. For the purposes of this treatise, and for the following MATLAB examples, the field of real numbers, R, will be used most often. The reader is urged to remember that any choice of field is allowed.
As a direct generalization of a vector space, a moduleM replaces the underlying field by a ring R. Technically speaking, M is a left module because the scalar appears left of the module element. In an analogous fashion, a moduleMover the ringR is an R-moduleM. From this discussion, it is apparent that if R is also a field, R-modules are merely vector spaces. In working with modules, it is important to remember to avoid any vector space results relying on division by a nonzero scalar. It is precisely this notion that leads to the extremely powerful application of modules in system analysis, controllability, and observability.
Tom St Denis , Simon Johnson , in Cryptography for Developers, 2007
SubBytes
The SubBytes step of the round function performs the nonlinear confusion step of the SPN. It maps each of the 16 bytes in parallel to a new byte by performing a two-step substitution (Figure 4.4).
Figure 4.4. AES SubBytes Function
The substitution is composed of a multiplicative inversion in GF(2)[x]/v(x) followed by an affine transformation (Figure 4.5) in GF(2)8. The multiplicative inverse of a unit a is another unit b, such that ab modulo the AES polynomial is congruent (equivalent to, or equal to when reduced by v(x)) to the polynomial p(x) = 1. For AES, we make the exception that the inverse of a(x) = 0 is itself.
Figure 4.5. AES Affine Transformation
There are several ways to find the inverse. Since the field is small, brute force requiring on average 128 multiplications can find it. With this approach we simply multiply a by all units in the field until the product is one.
It can also be found using the power rules. The order of the field GF(28) is 28 – 1 = 255 and a(x)254 = a(x)−1. Computing a(x)254 can be accomplished with eight squarings and seven multiplications. We list them separately, since squaring in GF(2) is a O(n) time operation (as opposed to the O(n2) that multiplication requires).
Here we used gf_mul to perform the squarings. However, there are faster and more hardware friendly ways of accomplishing this task. In GF(2)[x] the squaring operation is a simple bit shuffle by inserting zero bits between the input bits. For example, the value 11012 becomes 101000102. After the squaring, a reduction would be required. In software, for AES at least, the code space used to perform the function would be almost as large as the SubBytes function itself. In hardware, squaring comes up in another implementation trick we shall discuss shortly.
It can also be found by the Euclidean algorithm and finally by using log and anti-log (logarithm) tables. For software implementations, this is all overkill. Either the SubBytes step will be rolled into ShiftRows and MixColumns (as we will discuss shortly), or is implemented entirely as a single 8x8 lookup table.
After the inversion, the eight bits are sent through the affine transformation and the output is the result of the SubBytes function. The affine transform is denoted as
Where the vector <x0, x1, x2, …, x7> denotes the eight bits from least to most significant. Combined, the SubByte substitution table for eight bit values is as shown if Figure 4.6.
Figure 4.6. The AES SubBytes Table
The inverse of SubBytes is the inverse of the affine transform followed by the multiplicative inverse. It can be easily derived from the SubBytes table with a short loop.
Victor Sánchez Valencia , in Handbook of the History of Logic, 2004
A Contrast
Let us contrast a symbolical and a direct demonstration of a result obtained by Boole. We prove from α + α = 0 that α = 0.
Boole would have derived from the equation 2a = 0, dividing by 2, a = 0. The advantage of conciseness of this argument must not make us forget the advantages of the previous derivation. Therein it was clear that the deduction makes essential use of three pieces of algebraic information
–
The multiplicative inverse of 2 exists: 22−1 = 1.
–
1 is the unit element with regard to elective symbols: 1α = α.
–
A numerical product is zero when one of its factor is that.
Now I am ready to make a couple of general observation about Boole's proof strategy. In general, Boole avoids the use of symbolical arguments when an alternative is available. The unrestricted use of algebraic manipulations is limited to numerical expressions, including 0 and 1. This amount in his case to taking all their commutative ring properties for granted. He will, for instance, divide by 2 but not by α. Moreover, he will not feel compel to say that 0 ≠ 1 even though he considers the occurrence of the equation 1 = 0 as the indication that one has tried to "unite contradictory Propositions in a single equation" (p. 104). Likewise, he does not care to remind us that 1 denotes the unit element as far as the numerals are concerned but he points out that α · 1 = α (p. 60).
It must be admitted that within the framework of symbolical algebra he was not obligated to show such a reticence in the use of symbolical arguments. And he could not have been restrained by it, for not all the equations he uses are derivable from the Servois rules. For instance, three equations that are vital in his system and for which there is no direct Servois explanation are these
A + B = B + A
A(B – C) = AB – AC
α(1 – α) = 0
A symbolical explanation is, however, easy to find. The first two need no justification since they hold in ordinary algebra. For the last one, the supplementary law, Boole's symbolic argument would take this form. Since α = α2, transposing, α –a2 = 0. Hence, by factoring, α(1 – a) = 0.20
0 Response to "Multiplicative Inverse Definition and Example"
Post a Comment