Reduction of the coefficients of a polynomial in sage

edit

thank you mnTSW

@Max Alekseyev and if you wanted

64 <T <64 * j where j is an integer greater than 1

and 0< S <= sqrt(N) and 0< W <= sqrt(N)

How should i do?

In this case you need to take $C \approx \frac{\sqrt{N}}{64(j-1)}$ and use closest_vector(t) instead of shortest_vector(), with $t = ((64+32(j-1))C, \frac{\sqrt{N}}2, \frac{\sqrt{N}}2)$. That is, $t$ is formed by the medians of the ranges for $T,S,W$.

@Max Alekseyev for j = 100 Where am I wrong?

from sage.modules.free_module_integer import IntegerLattice

def mnTSW(N,a1,a2,a3,a4,b1,b2,b3,b4):
    C = max(round(sqrt(N)/(64*(100-1))),1)
    print("C =",C)
    M = matrix(ZZ,[(a1*a3*C,b1*b3*C,N*C,0,0),(a1*a4,-b1*b4,0,N,0),(a2*a3,-b2*b3,0,0,N)])
    L = IntegerLattice(M.transpose())
    TSW = L.closest_vector(((64+32*(100-1))*C,sqrt(N)/2,sqrt(N)/2))
    mn = M.solve_right(TSW)[:2] % N
    print("m,n =",mn)
    TSW = list(TSW)
    TSW[0] //= C
    print("T,S,W =",TSW)

mnTSW(390644893234047643,441692985,152029391,625015907,60099037,8,884426299,8,625015921)

It looks OK to me.

@Max Alekseyev What is the computational complexity over j and N? Maybe that's my problem. My computer does not output (only C).

It looks like CVP implementation in Sage uses a different approach than SVP (which is based on LLL) and is more time consuming. You'd need to re-implement it using LLL if you want better performance (in trade of accuracy) - e.g., see https://narkive.com/HLuYldXC

@Max Alekseyev

Thanks for everything.
One last question, if possible:
What is the computational cost of using LLL to find a single solution?

64 <T <64 * j where j is an integer greater than 1

and 0 <S <= sqrt (N) and 0 <W <= sqrt (N)


This computational cost would be the computational cost to factor N.

LLL has polynomial time - see https://en.wikipedia.org/wiki/Lenstra... But I doubt you'd be able to factor $N$ in polynomial time.

@Max Alekseyev I posted a free paper for you right now here https://mersenneforum.org/showthread.php?p=578212#post578212 (https://mersenneforum.org/showthread....)

@Max Alekseyev in the wikipedia you showed me, in the "Implementations" section it says that it is implemented in sage "SageMath as the method LLL driven by fpLLL and NTL". Would you help me, kindly?

You may find description of methods available in Sage at https://doc.sagemath.org/html/en/refe...

@Max Alekseyev thank you. It will take years to implement but I will make it. I am a beginner.

@Max Alekseyev I asked here https://ask.sagemath.org/question/57105/reduction-of-the-coefficients-of-a-polynomial-using-the-lll-algorithm/ (https://ask.sagemath.org/question/571...)