Questions and Answers #7 Polynomial Arithmetic

Questions and Answers Sheet 7 Polynomial Arithmetic Question #1 Using modular polynomial arithmetic, perform the following multiplication over 𝐺𝐹(23 ) with the irreducible polynomial 𝑥 3 + 𝑥 + 1. Convert the final result to decimal. 111 × 110 Answer: Irreducible polynomial is a polynomial that cannot be factorized into lower degree polynomials For the set of all polynomials over GF(2), let's now consider polynomial arithmetic modulo the irreducible polynomial 𝑥 3 + 𝑥 + 1. When an algebric operation results in a polynomial whose degree equals or exceeds that of the irreducible polynomial, we will take for our result the remainder modulo the irreducible polynomial. For example, (𝑥 2 + 𝑥 + 1) × (𝑥 2 + 1)𝑚𝑜𝑑(𝑥 3 + 𝑥 + 1) = (𝑥 4 + 𝑥 3 + 𝑥 2 ) + (𝑥 2 + 𝑥 + 1)𝑚𝑜𝑑(𝑥 3 + 𝑥 + 1) = (𝑥 4 + 𝑥 3 + 𝑥 + 1)𝑚𝑜𝑑(𝑥 3 + 𝑥 + 1) = −𝑥 2 − 𝑥 = 𝑥2 + 𝑥 Since 1+1=0 in GF(2). That's what caused the 𝑥 2 term to disappear in the second expression on the right hand side of the equality sign. With multiplications modulo (𝑥 3 + 𝑥 + 1), we have only the following eight polynomials in the set of polynomials over GF(2): 0 1 x 𝑥2 x+1 𝑥2 + 1 𝑥2 + 2 𝑥2 + 𝑥 + 1 We will refer to this set as 𝐺𝐹(23 ) where the exponent of 2, which in this case is 3, is the degree of the modulus polynomial. We can think of xi as being merely a place-holder for a bit i.e., we can think of the polynomials as bit strings corresponding to the coefficients that can only be 0 or 1, each power of x representing a specific position in a bit string. So the 23 polynomials of 𝐺𝐹(23 ) can therefore be represented by the bit strings: 0----000 1-----001 x-----010 𝑥 2 -----100 x+1 -----011 𝑥 2 + 1 ------101 𝑥 2 + 𝑥 ----110 𝑥 2 + 𝑥 + 1 ------111 If we wish, we can give a decimal representation to each of the above bit patterns. The decimal values between 0 and 7, both limits inclusive, would have to obey the addition and multiplication rules corresponding to the underlying finite field. Question #2 For polynomial arithmetic with coefficients in 𝑍10 , perform the following calculations. a. (7𝑥 + 2) − (𝑥 2 + 5) b. (6𝑥 2 + 𝑥 + 3) × (5𝑥 2 + 2) Answer: a. (7𝑥 + 2) − (𝑥 2 + 5) simplify given expression ⇒ 7𝑥 + 2 − 𝑥 2 − 5 ⇒ −𝑥 2 + 7𝑥 + (2 − 5) ⇒ −𝑥 2 + 7𝑥 − 3 To find coefficient in 𝑍10 ⇒ (−1𝑚𝑜𝑑10)𝑥 2 + (7𝑚𝑜𝑑10)𝑥 + (−3𝑚𝑜𝑑10) ⇒ (10 − 1)𝑥 2 + 7𝑥 + (10 − 3) = 9𝑥 2 + 7𝑥 + 7 b. 6𝑥 2 + 𝑥 + 3 × 5𝑥 2 + 2 12𝑥 2 + 2𝑥 + 6 30𝑥 4 + 5𝑥 3 + 15𝑥 2 30𝑥 4 + 5𝑥 3 + 27𝑥 2 + 2𝑥 + 6 To find coefficient in 𝑍10 (30𝑚𝑜𝑑10)𝑥 4 + (5𝑚𝑜𝑑10)𝑥 3 + (27𝑚𝑜𝑑10)𝑥 2 + (2𝑚𝑜𝑑10)𝑥 + (6𝑚𝑜𝑑10) ⇒ 0 ⋅ 𝑥 4 + 5𝑥 3 + 7𝑥 2 + 2𝑥 + 6 5𝑥 3 + 7𝑥 2 + 2𝑥 + 6 a. (7𝑥 + 2) − (𝑥 2 + 5) ≡ 10𝑥 2 − 𝑥 2 + 7𝑥 + 10 − 3 in 𝑍10 ≡ 9𝑥 2 + 7𝑥 + 7 b. 30𝑥 4 + 5𝑥 3 + 27𝑥 2 + 2𝑥 + 6 ≡ 5𝑥 3 + 7𝑥 2 + 2𝑥 + 6 in 𝑍10 see that 30=0 and 27=7 in 𝑍10 Question #3 For polynomial arithmetic with coefficients in 𝑍11 , perform the following calculations. a. (𝑥 2 + 2𝑥 + 9)(𝑥 3 + 11𝑥 2 + 𝑥 + 7) b. (8𝑥 2 + 3𝑥 + 2)(5𝑥 2 + 6) Answer: a. (𝑥 2 + 2𝑥 + 9)(𝑥 3 + 11𝑥 2 + 𝑥 + 7) = 𝑥 5 + 11𝑥 4 + 𝑥 3 + 7𝑥 2 + 2𝑥 4 + 22𝑥 3 + 2𝑥 2 + 14𝑥 + 9𝑥 3 + 99𝑥 2 + 9𝑥 + 63 = 𝑥 5 + 13𝑥 4 + 32𝑥 3 + 108𝑥 2 + 23𝑥 + 63 In coefficients 𝑍11 = 𝑥 5 + 2𝑥 4 + 10𝑥 3 + 9𝑥 2 + 𝑥 + 8 [Noti:-1%11=1, 13%11=2, 32%11=10, 108%11=9, 23%11=1, 63%11=8] b. (8𝑥 2 + 3𝑥 + 2)(5𝑥 2 + 6) = 40𝑥 4 + 58𝑥 2 + 15𝑥 3 + 18𝑥 + 12 In 𝑍11 coefficients, = 7𝑥 4 + 4𝑥 3 + 3𝑥 2 + 7𝑥 + 1 [ Noti:-40%11=7, 58%11=3, 15%11=4, 18%11=7, 12%11=1] Question #4 Consider 𝐴(𝑥) = 𝑥 3 + 𝑥 2 + 1 and 𝑏(𝑥) = 𝑥 2 + 𝑥 + 1 in GF(17). Also, the irreducible polynomial is given as 𝑝(𝑥) = 𝑥 3 + 1 1. Find 𝐴2 (𝑥)— 𝐵(𝑥). (13 pts) Hint: Use p(x) if the initial result does not fall in GF(17). Answer: Given that 𝐴(𝑥) = 𝑥 3 + 𝑥 2 + 1 𝐵(𝑥) = 𝑥 2 + 𝑥 + 1 𝑝(𝑥) = 𝑥 3 + 1 ⇒ 𝐴2 (𝑥) − 𝐵(𝑥) ⇒ 𝐴2 (𝑥) = (𝑥 3 + 𝑥 2 + 1) ⇒ (𝑥 3 + 𝑥 2 + 1)(𝑥 3 + 𝑥 2 + 1) ⇒ 𝑥6 + 𝑥5 + 𝑥3 + 𝑥5 + 𝑥4 + 𝑥2 + 𝑥3 + 𝑥2 + 1 ⇒ 𝐴2 (𝑥) = 𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1 ⇒ 𝐴2 (𝑥) − 𝐵(𝑥) ⇒ 𝑥 6 + 2𝑥 5 + 2𝑥 3 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1 − 𝑥 2 − 𝑥 − 1 ⇒ 𝑥 6 + 2𝑥 5 + 2𝑥 3 + 𝑥 4 + 𝑥 2 − 𝑥 𝐴2 (𝑥) − 𝐵(𝑥) = 𝑥 6 + 2𝑥 5 + 2𝑥 3 + 𝑥 4 + 𝑥 2 − 𝑥 Question #5 a) Find all positive ' numbers p s.t. x-2 is a factor of 𝑥 4 − 𝑥 3 + 𝑥 2 − 𝑥 + 5 in 𝑍𝑃 [𝑥]. Result 𝑎 = [𝑎]𝑝 is the congruence dass in 𝑍𝑝 of integer a. b) Let R be a ring with identity. Prove that x cannot be a zero diviser in 𝑅[𝑥] . (Polinomial Arithmetic problem.) Answer: a) 𝑝(𝑥) = 𝑥 4 − 𝑥 3 + 𝑥 2 − 𝑥 + 2 has x-2 as a factor iff p(2) = 0  24 − 23 + 22 − 2 + 2 = 0 in 𝑍𝑝 𝑟𝑖𝑔ℎ𝑡 ⇒ 16 − 8 + 4 = 0 in 𝑍𝑝 𝑟𝑖𝑔ℎ𝑡 ⇒ 22 ≡ 0 in 𝑍𝑝 𝑟𝑖𝑔ℎ𝑡 ⇒ 2 ⋅ 11 ≡ 0 in 𝑍𝑝 𝑟𝑖𝑔ℎ𝑡 ⇒ 𝑝 = 2 ≡ 𝑝 = 11 b) x can`t be a zero divisor in R[x]  ax = 0right  a = 0, a  IR   xa = 0right  a = 0, a  IR    𝑥𝑝(𝑥) = 0𝑟𝑖𝑔ℎ𝑡 ⇒ 𝑝(𝑥) = 0 as otherwise for 𝑝(𝑥) ≠ 0, 𝑥𝑝(𝑥) is a polynomial of degree >p(x) Similarly, 𝑝(𝑥)𝑥 = 0𝑟𝑖𝑔ℎ𝑡 ⇒ 𝑝(𝑥) = 0 Question #6 Consider 𝐴(𝑥) = 𝑥 3 + 𝑥 2 + 1 and 𝐵(𝑥) = 𝑥 2 + 𝑥 + 1 in GF(17). Also, the irreducible polynomial is given as 𝑝(𝑥) = 𝑥 3 + 1 1. Find 𝐴2 (𝑥)— 𝐵(𝑥). (13 pts) Hint: Use p(x) if the initial result does not fall in GF(17). 2. Find 𝐴2 (𝑥) ⋅ 𝐵2 (𝑥). (12 pts) Hint: Use p(x) if the initial result does not fall in GF(17) . Answer: 1) Find 𝐴2 (𝑥) − 𝐵(𝑥) 𝐴2 (𝑥) = (𝑥 3 + 𝑥 2 + 1)2 = (𝑥 3 + 𝑥 2 + 1)(𝑥 3 + 𝑥 2 + 1) = 𝑥6 + 𝑥5 + 𝑥3 + 𝑥5 + 𝑥4 + 𝑥2 + 𝑥3 + 𝑥2 + 1 = 𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1 𝐴2 (𝑥) = 𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1 ⇒ 𝐴2 (𝑥) − 𝐵(𝑥) = x 6 + 2 x5 + 2 x3 + x 4 + 2 x 3 + 2 x 2 + 1 − x 2 − x − 1 = 𝑥 6 + 2𝑥 5 + 2𝑥 3 + 𝑥 4 + 𝑥 2 − 𝑥 𝐴2 (𝑥) − 𝐵(𝑥) = 𝑥 6 + 2𝑥 5 + 2𝑥 3 + 𝑥 4 + 𝑥 2 − 𝑥 2) Find 𝐴2 (𝑥) ⋅ 𝐵2 (𝑥) 𝐴2 (𝑥) = 𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1 𝐵2 (𝑥) = (𝑥 2 + 𝑥 + 1)(𝑥 2 + 𝑥 + 1) = 𝑥4 + 𝑥3 + 𝑥2 + 𝑥3 + 𝑥2 + 𝑥 + 𝑥2 + 𝑥 + 1 = 𝑥 4 + 2𝑥 3 + 3𝑥 2 + 2𝑥 + 1 𝐵2 (𝑥) = 𝑥 4 + 2𝑥 3 + 3𝑥 2 + 2𝑥 + 1 𝐴2 (𝑥) ⋅ 𝐵2 (𝑥) = (𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 3 + 2𝑥 2 + 1) ⋅ (𝑥 4 + 2𝑥 3 + 3𝑥 2 + 2𝑥 + 1) = 𝑥 10 + 2𝑥 9 + 3𝑥 8 + 2𝑥 7 + 𝑥 6 + 2𝑥 9 + 4𝑥 8 + 6𝑥 7 + 4𝑥 6 + 2𝑥 5 + 𝑥 8 + 2𝑥 7 + 3𝑥 6 + 2𝑥 5 + 𝑥 4 + 2𝑥 7 + 4𝑥 6 + 6𝑥 5 + 4𝑥 4 + 2𝑥 3 + 2𝑥 6 + 4𝑥 5 + 6𝑥 4 + 4𝑥 3 + 2𝑥 2 + 𝑥 4 + 2𝑥 3 + 3𝑥 2 + 2𝑥 + 1 = 𝑥 10 + 4𝑥 9 + 8𝑥 8 + 12𝑥 7 + 14𝑥 6 + 14𝑥 5 + 12𝑥 4 + 8𝑥 3 + 5𝑥 2 + 2𝑥 + 1 ∴ 𝐴2 (𝑥) 𝐵2 (𝑥) = 𝑥 10 + 4𝑥 9 + 8𝑥 8 + 12𝑥 7 + 14𝑥 6 + 14𝑥 5 + 12𝑥 4 + 8𝑥 3 + 5𝑥 2 + 2𝑥 + 1 ∴ If you Impress with answer, please give me like. Question #7 Determine the multiplicative inverse of (𝑥 3 + 𝑥 + 1) in GF (24 ) with 𝑚(𝑥) = 𝑥 4 + 𝑥 + 1. Answer: (x3+x+1) in GF (x3+x+1) with m(x)=x4+x+1 . 𝑥 ∧ 4 + 𝑥 + 1 = 𝑥(𝑥 ∧ 3 + 𝑥 + 1) + (𝑥 ∧ 2 + 1) 𝑥 ∧ 3 + 𝑥 + 1 = 𝑥(𝑥 ∧ 2 + 1) + 1 1 = 𝑥 ∧ 3 + 𝑥 + 1 + 𝑥(𝑥 ∧ 2 + 1) 𝑥 ∧ 2 + 1 = 𝑥 ∧ 4 + 𝑥 + 1 + 𝑥(𝑥 ∧ 3 + 𝑥 + 1) ⇒ 1 = 𝑥 ∧ + 𝑥 + 1 + 𝑥(𝑥 ∧ + 𝑥 + 1 + 𝑥(𝑥 ∧ + 𝑥 + 1)) 1 = (𝑥 ∧ 2 + 1)(𝑥 ∧ + 𝑥 + 1) + 𝑥(𝑥 ∧ 4 + 𝑥 + 1) The final result is (𝑥 ∧ 3 + 𝑥 + 1)∧ − 1 = 𝑥 ∧ 2 + 1 Question #8 The polynomial 𝑦 = −0.79𝑥 4 + 3𝑥 3 + 27.3 shows the billions of flu virus particles in a person's body x days after being infected. Calculate the number of virus particles, in billions, after 1 day. Answer: We name, 𝑦 = −0.79𝑥 4 + 3𝑥 3 + 27.3 Where, x is number of days. Number of virus particles, in billions after 1 day For x=1 day 𝑦 = −0.79 ∗ 14 + 3 ∗ 13 + 27.3 𝑦 = − 0.79 + 3 + 27.3 𝑦 = 30 ∗ 221 There are 30*221 billion virus particles in a person's body 1 day after being infected. Question #9 How many times a particular number is a zero for a given polynomial. For example, in the polynomial function 𝑓(𝑥) = (𝑥 − 3)4 (𝑥 − 5)(𝑥 − 8)2 , the zero 3 has multiplicity 4, 5 has multiplicity 1, and 8 has multiplicity 2. Although this polynomial has only three zeros, we say that it has seven zeros counting multiplicity. Answer: In your example, 3 is a zero of f, because f(3)=0. That's all it means to call something a zero of a polynomial. If n is some number, and g(x) is a polynomial, we say n is a zero of g(n)=0 Now, if we have two polynomials with different zeros, we know the polynomials are different, but how can we tell if f(x)=(x-2)(x-3) and 𝑔(𝑥) = (𝑥 − 2)(𝑥 − 3)3 are different? They both have 2 and 3 as their roots, so that won't be quite enough to distinguish them. That's where the multiplicity of a root comes in. We say 3 is a zero of multiplicity 1 for f, whereas 3 is a zero of multiplicity 2 for g Another way to look at this, is if we look at f(x) without the factor of x-3, namely, the polynomial 𝑓(𝑥) 𝑓 ′ (𝑥) = = 𝑥 − 2, 𝑥−3 we can see 𝑓 ′ (3) = 3 − 2 = 1 ≠ 0. However, if we look at 𝑔′ (𝑥) = 𝑔(𝑥) 𝑥−3 = (𝑥 − 2)(𝑥 − 3) we have g'(3)=0. So in some sense, the multiplicity can be thought of as ''how many times can we remove the zero from the polynomial, until it's no longer a zero?'' Caution: When I write the divisions above, do not try to plug the zeros in to them. I.e., you cannot say 𝑓(3) 0 𝑓 ′ (3) = = , 3−3 0 which I claimed was 1 earlier, as you cannot divide by 0. Question #10 Find S for each arithmetic series described 𝑆13 ; 𝑎1 = 16, 𝑎𝑛 = 98 Answer: Step 1 The sum of n terms of AP is the sum (additim) of fin of n terms of the arithmetic sequence. 𝑛 𝑆𝑛 = (𝑎1 + 𝑎𝑛 ). 2 Step 2 So 11 (1𝑎) Given 𝑎1 = 16, 𝑎𝑛 = 98 We have to find 𝑆13 . So here n=13. We know that, 𝑛 Sum the arithmetic series 𝑆𝑛 = (𝑎1 + 𝑎𝑛 ) 2 Where 𝑎1 = 1𝑠𝑡 term of the series 𝑎𝑛 = last term of the series Here 𝑆𝑛 = = 13 2 × 114 = 741 13 2 (16 + 98)