In this project you need to write a program called "GF2.java" to implement the finite field GF(pn)where p is a prime number andn is a positive integer.You also need to write four methodsto realize "+","-","´", and "/".
Specifically, your program will read parameters and polynomialsfrom a file named "input.txt" (under the same directory).Then your program needs tocreate a file named "output.txt" (under the same directory) and prints the results to "output.txt".
In "input.txt":
1. First line is the prime number p.
2. Second line is the degree n of the irreducible polynomial m(x) over Zp.
3. Third line is the coefficients of m(x), from leading coefficient to the constant, separated by one blank space.
4. Fourth Line is the degree of f(x) over Zp.
5. Fifth line is the coefficients of f(x), from leading coefficient to the constant, separated by one blank space.
6. Sixth line is the degree of g(x) over Zp.
7. Seventh line is the coefficients of g(x), from leading coefficient to the constant, separated by one blank space.
In "output.txt":
1. First line is the coefficients of f(x)+g(x) (mod m(x)), from leading coefficient to the constant, separated by one blank space.
2. Second line is the coefficients of f(x)-g(x) (mod m(x)), from leading coefficient to the constant, separated by one blank space.
3. Third line is the coefficients of f(x)*g(x) (mod m(x)), from leading coefficient to the constant, separated by one blank space.
4. Fourth line is the coefficients of f(x)/g(x) (mod m(x)), from leading coefficient to the constant, separated by one blank space (don't forget to handle the case of g(x) = 0).
Important: leading coefficient should not be 0 unless the polynomial is 0.
Example 1: if p = 3, m(x) = x2 + 1, f(x) = 2x, g(x) = x + 1, then f(x) + g(x) = 1 instead of 0x + 1. Thus in the first line of "output.txt" it should print 1 instead of 0 1.
Example 2: if p = 3, m(x) = x2 + 1, f(x) = 2x + 2, g(x) = x + 1, then f(x) + g(x) = 0 instead of 0x + 0. Thus in the first line of "output.txt" it should print 0 instead of 0 0.
/** * PLDA (Polynomial long division algorithm) over GF(p) * * @param n(x) a polynomial * @param d(x) a non-zero polynomial * @param p a prime number * * @return quotient q(x) and remainder r(x) such that n(x) = q(x)*d(x) + r(x) mod p where deg(r(x))
n(x) = n(x) mod p // perform mod p to every coefficient of n(x)
d(x) = d(x) mod p // perform mod p to every coefficient of d(x)
(q(x), r(x)) <- (0, n(x))
while r(x) != 0 and deg(r(x)) >= deg(d(x)) do
t(x) <- lead(r(x))/lead(d(x)) /*
* lead() returns the leading term of a polynomial; the division requires EEA.
* E.g. if r(x) = 2x^2 + x + 1, d(x) = 3x + 2, and p = 7,
* then lead(r(x)) = 2x^2, lead(d(x)) = 3x,
* thus t(x) = 2x^2/3x = (2/3)(x^2/x) = 3x,
* here it needs EEA to compute 2/3 mod 7 = 3.
*/ (q(x), r(x)) <- (q(x) + t(x) mod p, r(x) - t(x)*d(x) mod p) return (q(x), r(x))
/** * EEAP (Extended Euclidean Algorithm for Polynomials) over GF(p)
* * @param a(x) a polynomial
* @param b(x) another polynomial
* @param p a prime number
* * @return polynomial array (u(x),v(x)) satisfying u(x)*a(x) + v(x)*b(x) = gcd(a(x),b(x)) mod p
*/EEAP(a(x), b(x))
a(x) = a(x) mod p // perform mod p to the coefficients of a(x)
b(x) = b(x) mod p // perform mod p to the coefficients of b(x)
if b(x) = 0 then
return (1/(leading coefficient of a(x)), 0) // gcd(a(x),0) should be monic
else Q = PLDA(a(x), b(x))
q(x) = Q[0] and r(x) = Q[1]
R = EEAP(b(x), r(x))
return (R[1] mod p, R[0]-q*R[1] mod p)