# ...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?

( 2018-01-17 17:29:42 +0200 )edit

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...

( 2018-01-17 23:25:52 +0200 )edit

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

( 2018-01-18 01:04:15 +0200 )edit

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.

( 2018-01-18 09:33:48 +0200 )edit

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.

( 2018-01-18 22:43:14 +0200 )edit