Here is the Code package polynomial;
import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException;
class PolyFunction { private int degree; private int coeff[];
PolyFunction(int deg, int coef) { this.coeff = new int [deg+1]; this.coeff[deg] = coef; this.degree = deg; } int getDegree() { int d = 0; for (int i = 0; i < coeff.length; i++) if (coeff[i] != 0) d = i; return d; } void checkMode(int primeNumber) { for (int i = 0; i <= getDegree(); i++) { coeff[i] %= primeNumber; if (coeff[i] < 0) coeff[i] += primeNumber; } } PolyFunction addition(PolyFunction gx,int primeNumber) { PolyFunction fx = this; PolyFunction fPlusG = new PolyFunction(Math.max(fx.degree, gx.degree),0); for (int i = 0; i <= fx.degree; i++) { fPlusG.coeff[i] += fx.coeff[i]; } for (int i = 0; i <= gx.degree; i++) { fPlusG.coeff[i] += gx.coeff[i]; } fPlusG.checkMode(primeNumber); return fPlusG; } PolyFunction minus(PolyFunction gx, int primeNumber) { PolyFunction fx = this; PolyFunction fMinusg = new PolyFunction(Math.max(fx.degree, gx.degree), 0); for (int i = 0; i <= fx.degree; i++) { fMinusg.coeff[i] += fx.coeff[i]; } for (int i = 0; i <= gx.degree; i++) { fMinusg.coeff[i] -= gx.coeff[i]; } fMinusg.checkMode(primeNumber); //fMinusg.degree = fMinusg.getDegree(); return fMinusg; } PolyFunction multiple(PolyFunction gx) { PolyFunction fx = this; PolyFunction fMulg = new PolyFunction(fx.degree + gx.degree, 0); for (int i = 0; i <= fx.degree; i++) for (int j = 0; j <= gx.degree; j++) fMulg.coeff[i+j] += (fx.coeff[i] * gx.coeff[j]); return fMulg; } PolyFunction[] PLDA(PolyFunction gx, int primeNumber) { PolyFunction fx = this; fx.checkMode(primeNumber); gx.checkMode(primeNumber); PolyFunction []qr = new PolyFunction[2]; qr[1] = fx; qr[0] = new PolyFunction(0,0); int degofQ = fx.getDegree() - gx.getDegree() ; if (degofQ == 0 && gx.getDegree() == 0) { //System.out.println("deg is zero"); int temp [] = EEA(primeNumber, gx.coeff[0]); int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]); divResult %= primeNumber; if ( divResult < 0) divResult += primeNumber; qr[0] = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult); qr[1] = new PolyFunction(0, 0); return qr; } if (degofQ < 0) { qr[1] = gx; qr[0] = fx; return qr; } while((qr[1].getDegree() >= gx.getDegree()) && (qr[1].getDegree()!=0 && qr[1].coeff[0]!=0)) { int [] temp = EEA(primeNumber,gx.coeff[gx.getDegree()]); int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]); divResult %= primeNumber; if ( divResult < 0) divResult += primeNumber; PolyFunction tx = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult); qr[0] = qr[0].addition(tx,primeNumber); PolyFunction txgx = tx.multiple(gx); qr[1] = qr[1].minus(txgx,primeNumber); qr[0].checkMode(primeNumber); qr[1].checkMode(primeNumber); } return qr; } PolyFunction[] EEAP(PolyFunction gx,int primeNumber) { PolyFunction fx = this; PolyFunction []qr = new PolyFunction[2]; if ((gx.getDegree() == 0) && gx.coeff[0] == 0) { int [] temp = EEA(primeNumber,fx.coeff[fx.getDegree()]); int divResult = (1 * temp[1]); divResult %= primeNumber; if ( divResult < 0) divResult += primeNumber; qr[0] = new PolyFunction(0, divResult); qr[1] = new PolyFunction(0, 0); return qr; } else { PolyFunction []R = new PolyFunction[2]; qr = fx.PLDA(gx,primeNumber); PolyFunction q = qr[0]; PolyFunction r = qr[1]; R = gx.EEAP(r,primeNumber); PolyFunction ux = R[1]; ux.checkMode(primeNumber); PolyFunction vx = R[0].minus(q.multiple(R[1]), primeNumber); vx.checkMode(primeNumber); return new PolyFunction[]{ux,vx}; } } public int[] EEA(int a, int b){ if(b == 0){ return new int[]{1,0}; } else { int q = a/b; int r = a%b; int[] R = EEA(b,r); return new int[]{R[1], R[0]-q*R[1]}; } } public String toString() { if (degree == 0) return "" + coeff[0]; if (degree == 1) return coeff[1] + "x + " + coeff[0]; String ret = coeff[getDegree()] + "x^" + getDegree(); for (int i = getDegree()-1; i >= 0; i--) { if (coeff[i] == 0) continue; else if (coeff[i] > 0) ret = ret + " + " + ( coeff[i]); else if (coeff[i] < 0) ret = ret + " - " + (-coeff[i]); if (i == 1) ret = ret + "x"; else if (i > 1) ret = ret + "x^" + i; } return ret; }
}
public class GF2 { private PolyFunction fx; private PolyFunction gx; private PolyFunction mx; private int primeNumber;
GF2(String file) { fx = gx = mx = null; if (readInput(file) == -1) return; System.out.println("PrimeNumber is " + primeNumber); System.out.println("mx is " + mx); System.out.println("fx is " + fx); System.out.println("gx is " + gx); } private int readInput(String file) { int mxDeg = 0, fxDeg = 0, gxDeg = 0; try { int counter = 1; FileReader fileReader = new FileReader(file); BufferedReader bufferedReader = new BufferedReader(fileReader); String data = null; while(( data= bufferedReader.readLine()) != null) { switch(counter) { case 1: primeNumber = Integer.parseInt(data); break; case 2: mxDeg = Integer.parseInt(data); break; case 3: String [] mxToken = data.split("\\s+"); PolyFunction []p = new PolyFunction[mxToken.length+1]; for(int i=0; i < mxToken.length; i++) { p[i] = new PolyFunction(mxDeg-i, Integer.parseInt(mxToken[i])); } mx = p[0]; for(int i=1; i < mxToken.length; i++) mx = mx.addition(p[i],primeNumber); break; case 4: fxDeg = Integer.parseInt(data);; break; case 5: String [] fxToken = data.split("\\s+"); PolyFunction []pf = new PolyFunction[fxToken.length+1]; for(int i=0; i < fxToken.length; i++) { pf[i] = new PolyFunction(fxDeg-i, Integer.parseInt(fxToken[i])); } fx = pf[0]; for(int i=1; i < fxToken.length; i++) fx = fx.addition(pf[i], primeNumber); break; case 6: gxDeg = Integer.parseInt(data); case 7: String [] gxToken = data.split("\\s+"); PolyFunction []pg = new PolyFunction[gxToken.length+1]; for(int i=0; i < gxToken.length; i++) { pg[i] = new PolyFunction(gxDeg-i, Integer.parseInt(gxToken[i])); } gx = pg[0]; for(int i=1; i < gxToken.length; i++) gx = gx.addition(pg[i],primeNumber); break; } counter++; } bufferedReader.close(); } catch (FileNotFoundException e) { System.out.println("Input file is not able to open"); return -1; } catch (IOException e) { e.printStackTrace(); return -1; } return 0; } void dmas() { System.out.println("Addition is : " + fx.addition(gx, primeNumber)); System.out.println("Subtraction is : " + fx.minus(gx, primeNumber)); PolyFunction fMulg = fx.multiple(gx); if (fMulg.getDegree() >= mx.getDegree()) { fMulg = fMulg.PLDA(mx,primeNumber)[1]; fMulg.checkMode(primeNumber); } System.out.println("Multiplication is : " + fMulg.toString()); PolyFunction fDivg = mx.EEAP(gx,primeNumber)[1]; fDivg = fx.multiple(fDivg); if (fDivg.getDegree() >= mx.getDegree()) { fDivg = fDivg.PLDA(mx,primeNumber)[1]; fDivg.checkMode(primeNumber); } System.out.println("Division is : " + fDivg); } public static void main(String[] args) { String file = "src\\polynomial\\myinput.txt"; GF2 obj = new GF2(file); obj.dmas(); }
}