BVA4

def generate_polynomial(F, q, f_x):
    n = f_x.degree()  # n = deg(f)
    QR.<x> = F.quotient(f_x)
    while 1:
        r = 1
        alpha = QR.random_element()
        phi = QR(x) - alpha
        g = alpha ** q
        while g!= alpha:
            r += 1
            phi *= (QR(x) - g)
            g = g ** q
        if r < n:
            continue
        phi = F(phi.list()) + f_x
        print("Generated polynomial: {}" . format(phi))
        return phi


def testBenOra(F, q, f_x, x):
    g = x
    n = f_x.degree()
    for i in range(0, int(n/2)):
        g = F(pow(g, q, f_x))
        if F.gcd(f_x, g - x) != 1:
            return False
    return True


def main():
    q = 2690663
    F = PolynomialRing(GF(q), 'x')
    f_x1 = F(x ** 18 + 2690564 * x ** 17 + 4590 * x ** 16 + 2558471 * x ** 15 + \
        2643840 * x ** 14 + 1495497 * x ** 13 + 2554912 * x ** 12 + 1163580 * x ** 11 + \
        392361 * x ** 10 + 728858 * x ** 9 + 1681172 * x ** 8 + 245680 * x ** 7 + \
        723405 * x ** 5 + 1512258 * x ** 4 + 137509 * x ** 3 + 1139068 * x ** 2 + \
        1685603 * x + 402025)  # Вариант 2 из ЛР4
    f_x2 = F(969823 + 957345 * x + 682546 * x ** 2 + 2109839 * x ** 3 + 614684 * x ** 4 + 379226 * x ** 5
       + 2118796 * x ** 6 + 660413 * x ** 7 + 2666566 * x ** 8 + 1855807 * x ** 9 + 2562208 * x ** 10
       + 2325361 * x ** 11 + 1612400 * x ** 12 + 846977 * x ** 13 + 1448900 * x ** 14 + 644655 * x ** 15
       + 917775 * x ** 16 + x ** 17) # ЛР 3
    f_x = generate_polynomial(F, q, f_x1)
    if testBenOra(F, q, f_x, f_x.variables()[0]):
        print("Polynomial is irreducible according to BenOra")
    else:
        print("Polynomial is reducible according to BenOra")
    if f_x.is_irreducible():
        print("Polynomial is irreducible according to Sage")
    else:
        print("Polynomial is reducible according to Sage")

main()