# ...some code above

P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
f = P(coef)
print(f(x=b)) # return 0, (b)**f.degree() < n(condition for coppersmith method)
print(f.small_roots(X = b + 1)) # return nothing(also without kwargs), but should contain b ?


Edit: Coef are list of coefficients, b is polynomial root(line 3). Why small._root didnt return list with b, if b is "small_root"- (b)**f.degree() < n(condition for coppersmith method)

edit retag close merge delete

what is coeff? What is b? What is your question?

The following code reproduces the problem:

N = 55555
R = Zmod(N)
P.<x> = PolynomialRing( R, implementation='NTL' )

for k in range(1,5):
f     = (x-7)^k*(x-5)*(x-43)*(x-273)    # 7, 43, 273 are here for making 2 a root
d     = f.degree()
roots = [ r for r in R if f(r) == R(0) ]
info  = ( str(roots) if len(roots)<10
else str(roots[:10]) + ( '... (totally %s roots)' % len(roots) ) )
print "k=%s" % k
print "          ROOTS: %s" % info
print "    SMALL ROOTS: %s" % f.small_roots()


The condition documented in

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots??


is an other one. Using set_verbose(2) we see that LLL is involved...

So what should i do ? I fault understanding meaning of function purpose or should i use other implementation ?

It would help if you described precisely what you want to do. We have no way to provide an alternative if we don't know what you are trying to achieve.

I just want to use coppersmith method, that said root can be found if |x| < N^(1/f.degree()). In @dan_fuelea's example no root can be found for k = 3, 4 even if should contains 2. 2^15 < 55555 , so also 2 < 55555^(1/7).

For small_root from documentation condition on bound is also true.