Skip to content

Instantly share code, notes, and snippets.

@halferty

halferty/lll.py

Created December 31, 2017 07:46
Show Gist options
  • Save halferty/c7123d79ef2e6566d6864a95b1096f9e to your computer and use it in GitHub Desktop.
Save halferty/c7123d79ef2e6566d6864a95b1096f9e to your computer and use it in GitHub Desktop.
Download ZIP
LLL
Raw
lll.py
zzz = 86
p = random_prime(2^512); q = random_prime(2^512)
N = p*q
a = p % 2^zzz
X = 2^zzz
M = matrix([[X^2, 2*X*a, a^2], [0, X, a], [0, 0, N]])
B = M.LLL()
x = PolynomialRing(RationalField(), 'x').gen()
Q = B[0][0]*x^2/X^2+B[0][1]*x/X+B[0][2]
foundp = a+Q.roots(ring=ZZ)[0][0]
[a, foundp, p, foundp == p]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment