LLL_for_poly_roots_mod_N_RSA_and_mapmakersdilemma.sagews

Let (f(x)) be a polynomial with integer coefficients (we can work multivariate too but with less certainty) for which we wish to find integer values, (n) such that (f(n) = 0 \mod{N}).

Generally this is a tough problem. However, if I'm ok just looking for small roots, namely (n \leq N^{1/(d^2)}) where (d) is the degree of (f) then I can win using LLL. The algorithm I will show here is the Hastad algorithm.

The key idea is that every integer multiple of (N) which is small enough must be 0

p = next_prime(7^10)
q = next_prime(47^5)
N = p*q

N^(2./7./8.) / sqrt(2.) #details at the bottom

2.81769924938516

N

64784297736947209

R.<q> = PolynomialRing(Zmod(N))
f = (R.random_element(5)+1 + q^6)*(q-2)
f

q^7 + 41633921413492341*q^6 + 60998603662550640*q^5 + 2879078942551391*q^4 + 30042416553427234*q^3 + 9247176457845341*q^2 + 54373526295713383*q + 4508581885703612

f.coeffs()

[4508581885703612, 54373526295713383, 9247176457845341, 30042416553427234, 2879078942551391, 60998603662550640, 41633921413492341, 1]

zf = f.change_ring(ZZ)

zf(2) % N

0

N

64784297736947209

[zf(i) % N for i in range(100)]

[4508581885703612, 9330412000442316, 0, 18652313227225262, 15631983524399765, 28679058313431834, 19486828499256881, 15474710565921788, 38501800969780616, 14873996040648307, 55350463812600673, 3816406256323159, 3798150810588063, 9723043630554565, 56884481187418457, 59210423217419643, 41815555337473375, 30925528484063757, 54663359334035020, 60345098496443981, 7421957423267562, 6500298565075991, 50949404613046262, 53724301933740193, 59835042722757704, 51403766244745474, 57936814266185316, 53537518785389638, 29765448481392284, 49789220670898168, 24695687825507905, 54151369229536196, 35730173039484827, 32946256694961129, 41521773205155550, 60869671628144305, 17301467584391681, 57234365700034709, 44280374714905481, 9393454152870795, 64035844604708361, 35500772571313444, 55293186869237955, 27470999016256342, 50044355179274009, 40256900787008660, 53787885757235415, 2189155599656558, 64242983133345137, 42064701921192813, 58969157688413731, 7729068247221093, 16675712720833788, 54897315695349058, 37005378775377629, 38763173121763093, 40517713338865700, 40631083291729317, 20636731957558922, 21257930259302509, 5366900196606399, 26158998169726669, 52698975126929649, 35897993167911408, 20568505392399642, 44419808046154168, 18347158175212691, 41504540947017347, 49828025110324509, 28911363595899867, 13822266414637314, 5427941327001096, 62367093231585102, 50394000377216662, 20859133452818028, 52208958289980816, 7995006336888912, 53588083483908599, 52852982869381884, 47449824721833171, 4801686604072468, 845883324249930, 60157323670500270, 42149730390865332, 26844807577130329, 34091996187529024, 48003283762531029, 22681579648980217, 63595548943430914, 7189332311320403, 18334595105663005, 2958782729065671, 38515705295275231, 8338114955740488, 59479719314874422, 5301996562552483, 5040530853951537, 58547553932740563, 602434158255575, 59574410673611018]

X = 3
R.<x> = PolynomialRing(ZZ)
bigf = zf(X*x)

zf.parent()
bigf.parent()

Univariate Polynomial Ring in q over Integer Ring Univariate Polynomial Ring in x over Integer Ring

M = identity_matrix(ZZ, bigf.degree()+1)
for p in range(bigf.degree()+1):
    M[p,p] = N*X^p
M.set_row(M.nrows()-1, bigf.coeffs())

M

[ 64784297736947209 0 0 0 0 0 0 0] [ 0 194352893210841627 0 0 0 0 0 0] [ 0 0 583058679632524881 0 0 0 0 0] [ 0 0 0 1749176038897574643 0 0 0 0] [ 0 0 0 0 5247528116692723929 0 0 0] [ 0 0 0 0 0 15742584350078171787 0 0] [ 0 0 0 0 0 0 47227753050234515361 0] [ 4508581885703612 163120578887140149 83224588120608069 811145246942535318 233205394346662671 14822660689999805520 30351128710435916589 2187]

Res = M.LLL()
Res

[ 3536594746393144 -8178140680896456 994441346759610 10825949704882086 -7948790913297582 -3500595829571931 5849036283930003 -3699856941265584] [ -7444858650269538 3802933319893683 590267597607810 8801225138601171 8943794353125801 7426164919467447 -5901596254493640 -3195727214437908] [ -5562741259189522 8652632506101843 4010796564808896 -1600219798664202 -7409915537488506 8916101129576970 -4599163726648992 -14024133352463850] [ 4495484926216244 -5702617823540724 -1267111621715481 -1856400995515095 5912403491716119 3459559304451492 -264394927587771 -20174812246233297] [ -1742743817588718 -12362424587778639 20570327545840560 1805144712052797 500008684708476 -1724073012971838 -1227216103419762 9280143733429431] [ 5845241985892600 -3251195242408392 -11518304481117990 -3645648502465302 -1618746884341758 24216272371220382 -2902161813772239 -1585172617992495] [ -1660345421202022 -5405008298512149 1073270785771161 400007860516242 7649267924244798 2303201178253413 30546397502971443 2941712772142104] [ 30676289488594617 32835143780430792 21476106269070624 676893194887320 5428365508316808 3386332510774857 12763994252609826 -2842439341732128]

def poly_from_row(matrix, row):
    coeffs = matrix.row(row)
    t = 0
    for i in range(len(coeffs)):
        t += x^i * coeffs[i]
    f = t(x/X)
    return f.change_ring(ZZ)

zpoly = poly_from_row(Res,0)
zpoly.parent()
zpoly(2)

Univariate Polynomial Ring in x over Integer Ring 0

zpoly.roots()

[(2, 1)]

So why/when does this work?

If the determinant of my lattice is (D) and it has dimension (d) then the first vector of an LLL reduced basis has norm ( \leq \alpha^{(d-1)/ 2}D^{1/d} ) where ( \alpha \approx \sqrt{4/3} ) (see worksheet on Lattice basics for more detail)

The lattice we designed has determinant ( = \prod(X^i N) = N^{d-1}X^{((d+1)d)/2} ) so LLL will give me something bounded by (\alpha^{(d-1)/2}(N^{d-1}X^{(d+1)d/2})^{1/(d+1)} ) (now (d) is the degree of the polynomial, sorry). So if (\alpha^{(d-1)/2}X^{(d+1)d/2} < N/\sqrt{d+1} ) then roots over the integers of that something (viewed as a polynomial) will be roots of the original polynomial modulo (N).

Coppersmith designed a larger family of polynomials whose lattice can find roots as large as ( N^{1/d}) which makes a more robust approach.