LLL_for_minimal_polynomials.sagews

In this application we want to take a root of an integer polynomial, known to (b) bits and recover the minimal polynomial

RR(sqrt(2))

1.41421356237310

myroot = 1.41421356237310

myroot.algdep(2)

x^2 - 2

%md 

$$ f(\sqrt{2}) = 0 $$ and $$f$$ has smallest degree and integer coefficients

$$ x^2 - 2 $$

$$f(\sqrt{2}) = 0$$$$x^2 - 2$$

R.<x> = PolynomialRing(ZZ)
g = R.random_element(6)
h = R.random_element(6)
f = g*h
CF = ComplexField(300)
alpha = f.roots(CF, multiplicities=False)[0]
f(alpha)

6.28363963558108998796258810238243282300827585599929544334278286999949472604379629626892529e-89

k = 7
C = 2^100 #big constant
I= identity_matrix(k)
X = Matrix(ZZ, k, 2, [[floor((C*alpha^i).real_part()), floor((C*alpha^i).imag_part())] for i in range(k)])
M = I.augment(X)
print M
res = M.LLL()
print res

[ 1 0 0 0 0 0 0 1267650600228229401496703205376 0] [ 0 1 0 0 0 0 0 -1895002387609032241502383015381 0] [ 0 0 1 0 0 0 0 2832826370608272188785197534723 0] [ 0 0 0 1 0 0 0 -4234773158327701095690599264811 0] [ 0 0 0 0 1 0 0 6330534016683163249908553545081 0] [ 0 0 0 0 0 1 0 -9463472879904721973005874507193 0] [ 0 0 0 0 0 0 1 14146882192351771155283682462779 0] [ -1 2 -4 14 3 -3 2 -4 0] [ 39868 33694 37362 4002 17898 27969 5358 -21339 0] [ -47568 4326 26 -15617 -1829 -43152 -27886 -23596 0] [ -11429 2931 -5864 -7487 60760 -36231 -51076 31209 0] [ -25611 -62206 107451 48905 1056 28955 5982 21067 0] [-107459 60950 10808 -4392 22977 47039 35499 30893 0] [ 19786 95515 4526 5910 -48495 -76165 -17365 71024 0]

coeffs = res.row(0)
factor = add([x^i * coeffs[i] for i in range(len(coeffs[:-2]))])
factor(alpha)

-4.90909346529772655309577195498627564297521551249944956511154911718710525472171585646009788e-91

factor, f/factor

(x^6 - 2*x^4 + x^3 - 15*x - 1, 16*x^3 - 2)

I = identity_matrix(3)
latex(I)

\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)

$$\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)$$