Ask Your Question
0

Reduction of the coefficients of a polynomial in sage

asked 2021-05-08 15:16:15 +0200

P_1_6 gravatar image

Given the two polynomials in two variables x and y

A(y,x)=((a1)*y+(a2))*((a3)*x+(a4))

B(y,x)=((b4)-(b3)*x)*((b2)-(b1)*y)

both congruent to zero mod a semiprimal number N

Is there a method in sage to reduce , the coefficients in x and y smaller than sqrt (N) and the coefficient in xy smaller than 64, of their linear combination of the same degree of polynomials A and B by exploiting the congruence?

Example

given the two polynomials in two variables x and y

A(y,x)=(25*y+11)*(27*x+1)

B(y,x)=(65-8*x)*(67-8*y)

both congruent to zero mod 1763

I had thought of finding m and n such that

m*(a1)*(a3)+n*(b1)*(b3) = N*t +T

m*(a1)*(a4)-n*(b1)*(b4) = N*s + S

m*(a2)*(a3)-n*(b2)*(b3) = N*w + W

T <= 64

S <= sqrt(N)

W <= sqrt(N)
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2021-05-10 01:44:43 +0200

Max Alekseyev gravatar image

If we understand "smaller" by absolute value, then the problem can be posed as finding a short vector in the lattice generated by column vectors: $$\begin{bmatrix} a_1a_3 C & b_1b_3 C & NC & 0 & 0 \\ a_1a_4 & -b_1b_4 & 0 & N & 0\\ a_2 a_3 & - b_2 b_3 & 0 & 0 & N \end{bmatrix}$$ where the constant $C:=\max\{1,\textrm{round}(\frac{\sqrt{N}}{64})\}$ is needed to make the coordinate of a short vector balanced. It is not guaranteed to produce a solution, but if it exists chances are high.

Here is a sample code:

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),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.shortest_vector()
    mn = M.solve_right(TSW)[:2] % N
    print("m,n =",mn)
    TSW = list(TSW)
    TSW[0] //= C
    print("T,S,W =",TSW)

mn(1012301,1001,2005,307,423,11,13,17,19)
edit flag offensive delete link more

Comments

thank you mnTSW

P_1_6 gravatar imageP_1_6 ( 2021-05-10 09:59:16 +0200 )edit

@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?
P_1_6 gravatar imageP_1_6 ( 2021-05-10 12:23:47 +0200 )edit

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 gravatar imageMax Alekseyev ( 2021-05-11 00:58:56 +0200 )edit

@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)
P_1_6 gravatar imageP_1_6 ( 2021-05-11 12:09:32 +0200 )edit

It looks OK to me.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-11 16:11:38 +0200 )edit

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

P_1_6 gravatar imageP_1_6 ( 2021-05-11 16:55:29 +0200 )edit

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 gravatar imageMax Alekseyev ( 2021-05-11 17:55:28 +0200 )edit

@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.
P_1_6 gravatar imageP_1_6 ( 2021-05-11 18:27:28 +0200 )edit

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 gravatar imageMax Alekseyev ( 2021-05-11 19:18:27 +0200 )edit

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

P_1_6 gravatar imageP_1_6 ( 2021-05-11 19:39:03 +0200 )edit

@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?

P_1_6 gravatar imageP_1_6 ( 2021-05-12 10:56:46 +0200 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-12 19:57:05 +0200 )edit

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

P_1_6 gravatar imageP_1_6 ( 2021-05-12 21:12:03 +0200 )edit

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

P_1_6 gravatar imageP_1_6 ( 2021-05-13 13:00:16 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-05-08 15:16:15 +0200

Seen: 188 times

Last updated: May 10