DALGLI0/zad2/PolynomialOperations.java

import java.util.Arrays;

public class PolynomialOperations {

    public static int[] multiple(int[] f, int[] g, int n) {
        int[] result = new int[f.length + g.length - 1];
        for (int i = 0; i < f.length; i++)
            for (int j = 0; j < g.length; j++)
                result[i + j] += f[i] * g[j];

        for (int i = 0; i < result.length; i++)
            result[i] = result[i] % n;
        return result;
    }

    private static int findFactor(int a, int b, int mod) {
        for (int i = 0; i < mod; i++)
            if (a == (b * i) % mod)
                return i;
        return Integer.MIN_VALUE;
    }

    private static int[] shr(int[] p, int shift) {
        if (shift <= 0)
            return p;
        int[] shiftedPoly = new int[p.length];
        for (int i = 0; i < p.length - shift; i++)
            shiftedPoly[i] = p[i + shift];
        return shiftedPoly;
    }

    private static void polyMultiply(int[] p, int n) {
        Arrays.stream(p).forEach(value -> value = value * n);
    }

    private static int[] polySubtract(int[] p, int[] s) {
        int result[] = Arrays.copyOf(p, p.length);
        for (int i = 0; i < p.length; ++i) {
            result[i] = p[i] - s[i];
        }
        return result;
    }

    private static int[] createNewPoly(int[] p, int size) {
        int[] tmpTab = new int[size];
        for (int j = 0; j < p.length; j++) {
            tmpTab[tmpTab.length - 1 - j] = p[p.length - 1 - j];
        }
        return tmpTab;
    }

    private static void applyModuloToTab(int p[], int mod) {
        Arrays.stream(p).forEach(value -> value = value % mod);
    }

    public static int[] divide(int[] n, int[] d, int mod) {
        if (n.length < d.length) {
            return null;
        }
        int nd = n.length - 1;
        int dd = d.length - 1;
        int index = 0;
        int[] tmpTab = createNewPoly(d, n.length);
        while (nd >= dd) {
            int factor = findFactor(n[nd], d[dd], mod);
            tmpTab = shr(tmpTab, index);
            polyMultiply(tmpTab, factor);

            applyModuloToTab(tmpTab, mod);
            tmpTab = polySubtract(n, tmpTab);
            nd--;
            index++;
        }
        return Arrays.copyOf(n, index - 1);
    }

    public static int[] NWD(int[] a, int[] b, int mod) {
        if (a.length <= 0 || b.length <= 0)
            return null;

        while (b.length != 0) {
            int[] c;
            if (a.length >= b.length)
                c = divide(a, b, mod);
            else
                c = divide(b, a, mod);
            a = b;
            b = c;
        }
        return a;
    }
}