CoCalc -- 2018-02-12-191035.sagews

Project: ack

Path: 2018-02-12-191035.sagews

Views: ³⁸

import time
 
debug = False
 
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print a
 
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham
   
    finds a solution if:
    * b|modulus, b >= modulus^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt
 
    #
    # checks
    #
    if not 0 < beta <= 1:
        raise ValueError("beta should belongs in (0, 1]")
 
    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")
 
    #
    # calculate bounds and display them
    #
    """
    * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
 
    * we know LLL will give us a short vector v such that:
    ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
 
    * we will use that vector as a coefficient vector for our g(x)
   
    * so we want to satisfy:
    2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
   
    so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
    (it's important to use N because we might not know b)
    """
    if debug:
        # t optimized?
        print "\n# Optimized t?\n"
        print "we want X^(n-1) < N^(beta*m) so that each vector is helpful"
        cond1 = RR(XX^(nn-1))
        print "* X^(n-1) = ", cond1
        cond2 = pow(modulus, beta*mm)
        print "* N^(beta*m) = ", cond2
        print "* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD"
       
        # bound for X
        print "\n# X bound respected?\n"
        print "we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M"
        print "* X =", XX
        cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
        print "* M =", cond2
        print "* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD"
 
        # solution possible?
        print "\n# Solutions possible?\n"
        detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
        print "we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)"
        cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
        print "* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1
        cond2 = RR(modulus^(beta*mm) / sqrt(nn))
        print "* N^(beta*m) / sqrt(n) = ", cond2
        print "* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)"
 
        # warning about X
        print "\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n"
   
    #
    # Coppersmith revisited algo for univariate
    #
 
    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()
 
    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
   
    # construct lattice B
    BB = Matrix(ZZ, nn)
 
    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]
 
    # display basis matrix
    if debug:
        matrix_overview(BB, modulus^mm)
 
    # LLL
    BB = BB.LLL()
 
    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii
 
    # factor polynomial
    potential_roots = new_pol.roots()
    #print "potential roots:", potential_roots
 
    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))
 
    #
    return roots
 
n = 4861568377570277275752593875623434833428987555694716050115072991487423164889168220683706188870174296519274413642173076753045942769614395506152513604931227
mprime = 2956671530241801401503589220072800242410
order = 720720
 
for a in range(160000,order):
    R.<x> = QQ[]
    f = x + (inverse_mod(mprime, n) * lift(Mod(65537, mprime) ** a)) % n
    beta = 0.5
    xx = 2*n^beta/mprime
    for root in coppersmith_howgrave_univariate(f, n, beta, 5, 6, xx):
        p = root*mprime+lift(Mod(65537, mprime) ** a)
        if n % p == 0:
            print "Success!!", [p, n/p]
    if not a % 1000:
        print a

Error in lines 73-83
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 6, in <module>
  File "", line 66, in coppersmith_howgrave_univariate
  File "sage/matrix/matrix_integer_dense.pyx", line 3169, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.LLL (build/cythonized/sage/matrix/matrix_integer_dense.c:27995)
    R = A.to_matrix(self.new_matrix())
  File "sage/matrix/matrix1.pyx", line 2368, in sage.matrix.matrix1.Matrix.new_matrix (build/cythonized/sage/matrix/matrix1.c:18419)
    return self.matrix_space(nrows, ncols, sparse=sparse)(entries=entries,
  File "sage/matrix/matrix1.pyx", line 2309, in sage.matrix.matrix1.Matrix.matrix_space (build/cythonized/sage/matrix/matrix1.c:18036)
    return MatrixSpace(base_ring, nrows, ncols, sparse)
  File "sage/misc/classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1589)
    return cls.classcall(cls, *args, **kwds)
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/matrix/matrix_space.py", line 149, in __classcall__
    @staticmethod
  File "src/cysignals/signals.pyx", line 251, in cysignals.signals.python_check_interrupt
  File "src/cysignals/signals.pyx", line 94, in cysignals.signals.sig_raise_exception
KeyboardInterrupt