ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 13 May 2021 13:00:16 +0200Reduction of the coefficients of a polynomial in sagehttps://ask.sagemath.org/question/57023/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) Sat, 08 May 2021 15:16:15 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/Answer by Max Alekseyev for <p>Given the two polynomials in two variables x and y</p>
<pre><code>A(y,x)=((a1)*y+(a2))*((a3)*x+(a4))
B(y,x)=((b4)-(b3)*x)*((b2)-(b1)*y)
</code></pre>
<p>both congruent to zero mod a semiprimal number N</p>
<p>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?</p>
<p>Example</p>
<p>given the two polynomials in two variables x and y</p>
<pre><code>A(y,x)=(25*y+11)*(27*x+1)
B(y,x)=(65-8*x)*(67-8*y)
</code></pre>
<p>both congruent to zero mod 1763</p>
<p>I had thought of finding m and n such that</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?answer=57047#post-id-57047If 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)Mon, 10 May 2021 01:44:43 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?answer=57047#post-id-57047Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57106#post-id-57106@Max Alekseyev I asked here https://ask.sagemath.org/question/57105/reduction-of-the-coefficients-of-a-polynomial-using-the-lll-algorithm/Thu, 13 May 2021 13:00:16 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57106#post-id-57106Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57089#post-id-57089@Max Alekseyev thank you.
It will take years to implement but I will make it.
I am a beginner.Wed, 12 May 2021 21:12:03 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57089#post-id-57089Comment by Max Alekseyev for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57088#post-id-57088You may find description of methods available in Sage at https://doc.sagemath.org/html/en/reference/modules/sage/modules/free_module_integer.htmlWed, 12 May 2021 19:57:05 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57088#post-id-57088Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57085#post-id-57085@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?Wed, 12 May 2021 10:56:46 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57085#post-id-57085Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57078#post-id-57078@Max Alekseyev I posted a free paper for you right now here https://mersenneforum.org/showthread.php?p=578212#post578212Tue, 11 May 2021 19:39:03 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57078#post-id-57078Comment by Max Alekseyev for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57077#post-id-57077LLL has polynomial time - see https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
But I doubt you'd be able to factor $N$ in polynomial time.Tue, 11 May 2021 19:18:27 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57077#post-id-57077Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57076#post-id-57076@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.Tue, 11 May 2021 18:27:28 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57076#post-id-57076Comment by Max Alekseyev for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57075#post-id-57075It 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/HLuYldXCTue, 11 May 2021 17:55:28 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57075#post-id-57075Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57073#post-id-57073@Max Alekseyev What is the computational complexity over j and N? Maybe that's my problem.
My computer does not output (only C).Tue, 11 May 2021 16:55:29 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57073#post-id-57073Comment by Max Alekseyev for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57071#post-id-57071It looks OK to me.Tue, 11 May 2021 16:11:38 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57071#post-id-57071Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57067#post-id-57067@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)Tue, 11 May 2021 12:09:32 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57067#post-id-57067Comment by Max Alekseyev for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57064#post-id-57064In 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$.Tue, 11 May 2021 00:58:56 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57064#post-id-57064Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57054#post-id-57054@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?Mon, 10 May 2021 12:23:47 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57054#post-id-57054Comment by P_1_6 for <p>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.</p>
<p>Here is a sample code:</p>
<pre><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)
</code></pre>
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57053#post-id-57053thank you
mnTSWMon, 10 May 2021 09:59:16 +0200https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/?comment=57053#post-id-57053