small_roots doesn't work with larger X?

asked 2021-08-04 14:11:59 +0200

OAO gravatar image

I already have lower bits of a factor of $N = pq$, and I try to use the following code to factorize $N$

PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()

f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X = 2 ** (nbits // 2 - kbits), beta = 0.3) ### Called it (@)

if roots:
    x0 = roots[0]
    p = gcd(2^kbits*x0 + p0, n)
    print(p)

However it doesn't find any root. But I change (@) to

roots = f.small_roots(X = 2 ** 60, beta = 0.3) ### nbits // 2 - kbits = 165

Then it successfully find the small root of $f$. I read the document but still don't know why the original code doesn't work. Need help QAQ

edit retag flag offensive close merge delete

Comments

Welcome to Ask Sage! Thank you for your question.

slelievre gravatar imageslelievre ( 2021-08-04 16:35:03 +0200 )edit

Could you please provide a complete example. How are n, kbits, x, p0 defined ?

tmonteil gravatar imagetmonteil ( 2021-08-07 17:05:40 +0200 )edit