Reduction of the coefficients of a polynomial in sage

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 close merge delete

Sort by » oldest newest most voted

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)

more

thank you mnTSW

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

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

( 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)

( 2021-05-11 12:09:32 +0200 )edit

It looks OK to me.

( 2021-05-11 16:11:38 +0200 )edit