a0, a1, a2 = var("a0, a1, a2")


# data una lista di 3 punti Pt, trova il polinomio di II grado
# che valutato su ciascuna delle ascisse dei tre punti
# vale il valore dell'ordinata:

def polinomio_per_punti(Pt):
    g = a0+a1*x+a2*x^2
    eqz = [g.subs({x:Pt[i][0]})-Pt[i][1] for i in range(3)]
    slz = solve(eqz, [a0, a1, a2], solution_dict=true)
    return(g.subs(slz[0]))

## esempio: trovare polinomio g di II grado tale che 
## g(1) = 3, g(2) = 5, g(-4) = 8
sage: polinomio_per_punti([(1, 3), (2, 5), (-4, 8)])
sage: 1/2*x^2 + 1/2*x + 2


# dato un polinomio f e un intero n0,
# restituisce tutti i divisori (positivi e negativi)
# di f valutato in n0. Se f(n0) = 0, restituisce la tupla 
# nulla.

def divisori_polinomio_valutato(f, n0):
    val_f = f.subs({x: n0})
    if val_f == 0:
        return()
    Div = ZZ(val_f).divisors()
    Div = Div + [-d for d in Div]
    return Div

## Esempio: 
sage: divisori_polinomio_valutato(x^4+3*x^2-2*x+5, 5)
sage: [1, 5, 139, 695, -1, -5, -139, -695]


# dato f DI GRADO 5 e tre interi n1, n2, n3,
# trova un fattore di f. Se f e' irriducibile, ritorna 1

def trova_fattore(f, n1, n2, n3):
    D1 = divisori_polinomio_valutato(f, n1)
    D2 = divisori_polinomio_valutato(f, n2)
    D3 = divisori_polinomio_valutato(f, n3)
    # questi 3 casi si hanno quando n1 o n2 o n3 e' uno zero di f
    if D1 == ():
        return(x-n1)
    if D2 == ():
        return(x-n2)
    if D3 == ():
        return(x-n3)
    tre_div = [[d1, d2, d3] for d1 in D1 for d2 in D2 for d3 in D3]
    for trn in tre_div:
        g = polinomio_per_punti([[n1, trn[0]], [n2, trn[1]], [n3, trn[2]]])
        if gcd(f,g) != 1:
            return(gcd(f, g))
    return(1)

## esempi:
sage: trova_fattore(x^5+4*x^4+4*x^3+25*x^2-8*x-2, 1, -1, 0)
sage: x^2 + 4*x - 2
sage: trova_fattore(x^5-32, 2, 3, 4)
sage: x-2
sage: trova_fattore(x^5-32, 5, 6, 4)
sage: x-2