Trouble with sage small_roots

asked 2018-01-17 15:46:20 +0200

cptYossarian1234 gravatar image

updated 2018-01-17 18:15:35 +0200

...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 flag offensive close merge delete

Comments

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

vdelecroix gravatar imagevdelecroix ( 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...

dan_fulea gravatar imagedan_fulea ( 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 ?

cptYossarian1234 gravatar imagecptYossarian1234 ( 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.

vdelecroix gravatar imagevdelecroix ( 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.

cptYossarian1234 gravatar imagecptYossarian1234 ( 2018-01-18 22:43:14 +0200 )edit
see more comments