Reduction of the coefficients of a polynomial in sage

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

P_1_6
17 ●3 ●5 ●11

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

add a comment

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

Max Alekseyev

6540 ●9 ●47 ●153

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

Comments

thank you mnTSW

P_1_6 ( 2021-05-10 09:59:16 +0100 )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 ( 2021-05-10 12:23:47 +0100 )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 ( 2021-05-11 00:58:56 +0100 )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 ( 2021-05-11 12:09:32 +0100 )edit

It looks OK to me.

Max Alekseyev ( 2021-05-11 16:11:38 +0100 )edit

see more comments

Reduction of the coefficients of a polynomial in sage

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Reduction of the coefficients of a polynomial in sage edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Reduction of the coefficients of a polynomial in sage