3748.sagews

N=10005875164201218085138277893557320818117283128285908602118141999893467541287795021702868912454106185756678349458139419940385898306386521590331924626668854123672136085616228449665949554569154559812703781139815223011924479851012853262710594238927292085512526552521432033314477812416715877018585950563682959619671600044927131334980900992007645313443087129979713484353771447525939048627601802095406926748318227530262456726374239172563990640705255349313885902033793822143972762428367161198434076410811463598230263054017985239182927588721258228781742501810006050866554584192961419761583114769702235201156342341322402530823

e=2125963540892179

dptil=106065845341213497426332573985368484400489218999488613024861985041880980238189307329529724261208701954403218002998598054683610287960649043659251650907827432252239075610867870586876781618163085013934492649743413618961344433443974946882479535242048127689593673579745459212313947997023872106502252698565910481085

kptil=dptil*e-1 # berechnet sich aus den gegebenen Werten

P,x=PolynomialRing(IntegerRing(),x).objgen()

X=ceil(RDF(N^(0.25))) # obere Schranke festlegen
f=x+kptil             # unser Ausgangspolynom

# ab hier bauen wir unsere Gitterbasis auf
m=5
b=1/2
dim=m/b
B=matrix(dim,dim);

# erste Haelfte
for i in range(m+1):
    pol=N^(m-i)*f^i;
    pol=pol.subs(x=x*X);
    coeffs=pol.coeffs();
    for j in range(len(coeffs)):
        B[i,j]=coeffs[j];
# zweite Haelfte
for i in range(m+1,dim):
    pol=x^(i-m)*f^m;
    pol=pol.subs(x=x*X);
    coeffs=pol.coeffs();
    for j in range(len(coeffs)):
        B[i,j]=coeffs[j];

# fuer den L3-Algorithmus importieren wir...
# http://flask.sagenb.org/src/libs/fplll/fplll.pyx
from sage.libs.fplll.fplll import FP_LLL
F=FP_LLL(B)
F.wrapper()
L=F._sage_() # unser Gitter nach der Reduktion

# Aufsummieren aller Zeilen des Gitters
pol=0;
for i in range(len(L[0])):
    pol+=(L[0][i]/(X^i))*(x^i)
    
# dann die Nullstelle(n) finden
x0=pol.roots()[0][0]

# woraus sich kp ergibt
kp=x0+kptil

# und hier das Ergebnis
if Integer(kp).divides(N):
    print "p=", kp
else:
    print "kein Erfolg"

kein Erfolg