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.Sat, 08 May 2021 15:17:35 +0200Bivariate Coppersmith methodhttps://ask.sagemath.org/question/56885/bivariate-coppersmith-method/Given the bivariate polynomial
p(m,n) = 675 * m * n + 297 * m + 25 * n + 11
The bivariate Coppersmith method can be used to find m0 and n0 such that
(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0
where is it
m0 = 3 ; n0 = 3
Unfortunately I cannot understand the hypotheses
Kindly someone could only explain the hypotheses to me
EDIT1:
OTHER INFORMATION
You can choose some coefficients and their size order of this type of polynomial in O (16).
(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
EDIT2:
At least see if I understand:
in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
Did I get it right ?Fri, 30 Apr 2021 19:21:39 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/Comment by P_1_6 for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56905#post-id-56905@Max Alekseyev I shared other information .[]
@Emmanuel Charpentier if the bivariate Coppersmith method is applicable is relevant to computation of factorizationSun, 02 May 2021 21:16:11 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56905#post-id-56905Comment by P_1_6 for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56899#post-id-56899@Max Alekseyev thank youSun, 02 May 2021 10:17:33 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56899#post-id-56899Comment by Max Alekseyev for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56897#post-id-56897Some implementation is available at https://github.com/ubuntor/coppersmith-algorithmSun, 02 May 2021 04:33:11 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56897#post-id-56897Comment by P_1_6 for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56893#post-id-56893@Emmanuel Charpentier is there any method to use bivariate coppersmith method in sagemath?Sat, 01 May 2021 10:06:06 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56893#post-id-56893Comment by Emmanuel Charpentier for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56892#post-id-56892Your question would be better addressed to [https://math.stackexchange.com/](https://math.stackexchange.com/) : this forum is oriented towards the use of Sagemath to execute mathematical computations ; mathematical foundations are discussed only when this is relevant to computation.Sat, 01 May 2021 07:14:30 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56892#post-id-56892Answer by Max Alekseyev for <p>Given the bivariate polynomial</p>
<p>p(m,n) = 675 * m * n + 297 * m + 25 * n + 11</p>
<p>The bivariate Coppersmith method can be used to find m0 and n0 such that</p>
<p>(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0</p>
<p>where is it</p>
<p>m0 = 3 ; n0 = 3</p>
<p>Unfortunately I cannot understand the hypotheses </p>
<p>Kindly someone could only explain the hypotheses to me</p>
<p>EDIT1:</p>
<p>OTHER INFORMATION</p>
<p>You can choose some coefficients and their size order of this type of polynomial in O (16).</p>
<pre><code>(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8
->
N=p*q
if we choose A such that p-A mod 8 = 0
we can write it this way
(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X
so there are 4 chances to find A and they are
8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7
(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8
->
N=p*q
if we choose B such that q-B mod 8 = 0
we can write it this way
(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y
so there are 4 chances to find B and they are
8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7
f(N,A,B) is O(16)
Example
1763=41*43
220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8
220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8
220-Q-[4-(25-7)*(25-5)/8]=25*X
220-P-[4-(27-7)*(27-5)/8]=27*X
Q=25*a+11 X=10-a
P=27*b+1 X=10-b
220-Q-[4-(17-7)*(17-5)/8]=17*X
Q=17*c+10 X=13-c 9-a=13-c -> c=a+4
220-P-[4-(19-7)*(19-5)/8]=19*X
P=19*d+9 X=12-d 9-b=12-d ->d=b+3
p=(19*(b+3)+9)-(27*b+1)=65-8*b
q=(17*(a+4)+10)-(25*a+11)=67-8*a
(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8
(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE
So I thought about using the bivariate Coppersmith method
Q=25*a+11
P=27*b+1
p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763
</code></pre>
<p>EDIT2:</p>
<p>At least see if I understand:</p>
<pre><code>in my case given two polynomials
for example
(25*a+11)*(27*b+1) mod 1763 ==0
and
(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0
the first question is can they be both modulo 1763?
|a|<IntegerPart[sqrt(1763/2)]
|b|<2*IntegerPart[sqrt(1763/2)]
if this method can be applied, it can be solved in polynomial time
</code></pre>
<p>Did I get it right ?</p>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?answer=56949#post-id-56949I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.
As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that
R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
Tue, 04 May 2021 16:41:47 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?answer=56949#post-id-56949Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57024#post-id-57024@Max Alekseyev
https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/Sat, 08 May 2021 15:17:35 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57024#post-id-57024Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57009#post-id-57009@Max Alekseyev
Given the two polynomials in two variables x and y
A(y,x)=((a1)*y+(a2))*(x*(a3)+(a4))
B(y,x)=((b4)-(b3)*x)*((b2)-(b1)*y)
both congruent to zero mod a semiprimal number N
Is there a method to reduce the coefficients in x and y smaller than sqrt (N) 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 1763Fri, 07 May 2021 16:09:28 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57009#post-id-57009Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57007#post-id-57007@Max Alekseyev thanks for your patienceFri, 07 May 2021 11:52:46 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=57007#post-id-57007Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56995#post-id-56995@Max Alekseyev
p(x, y) = a + bx + cy + dxy ;
X*Y < W^(2/3δ) ;
W = max{|a|, |b|X, |c|Y, |d|XY }
we can easily choose | d | XY of the order size N ^ 2 and X * Y of the order size of N.
that is the problem?Thu, 06 May 2021 18:08:58 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56995#post-id-56995Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56994#post-id-56994@Max Alekseyev thank youThu, 06 May 2021 17:28:02 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56994#post-id-56994Comment by Max Alekseyev for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56993#post-id-56993Is depends on the size of RSA modulus. Say, there is negligible chance with a 2048-bit, let along 4096-bit, modulus.Thu, 06 May 2021 16:14:10 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56993#post-id-56993Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56991#post-id-56991@Max Alekseyev the real question is this:
"RSA-based Ramsonware" can they be defeated in your opinion with this technique?Thu, 06 May 2021 10:45:39 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56991#post-id-56991Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56988#post-id-56988@Max Alekseyev
how is it solved and what is the computation cost to solve this?Wed, 05 May 2021 22:24:16 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56988#post-id-56988Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56987#post-id-56987@Max Alekseyev Thanks for your patience.
(25*a+11)*(27*b+1)-(65-8 * b) * (67-8 * a) mod 1763 = 0Wed, 05 May 2021 22:03:05 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56987#post-id-56987Comment by Max Alekseyev for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56986#post-id-56986No, as we see that `(25*a+11)*(27*b+1)` is reducible (product of 2 factors).Wed, 05 May 2021 21:55:42 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56986#post-id-56986Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56984#post-id-56984@Max Alekseyev Thanks for your patience. I ask you a question: how is it solved and what is the computation cost to solve this?
(25*a+11)*(27*b+1) mod 1763 = 0Wed, 05 May 2021 21:44:10 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56984#post-id-56984Comment by Max Alekseyev for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56982#post-id-56982I do not follow this question since it's about two polynomials, while Coppersmith method applies to a single polynomial.Wed, 05 May 2021 19:58:24 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56982#post-id-56982Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56981#post-id-56981@Max Alekseyev thank you.
Do you also know the answer to the third question of the comments? [multivariate]Wed, 05 May 2021 19:51:17 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56981#post-id-56981Comment by Max Alekseyev for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56980#post-id-56980Yes, Coppersmith method is applicable to `(65-8 * b) * (67-8 * a) -1763 = 0`, but not to `64*a^2*b^2-840*a^2*b+2600*a^2-856*a*b^2+10560*a*b-34800*a+2680*b^2-35472*b+108864=0` since the latter polynomial is reducible.Wed, 05 May 2021 19:26:05 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56980#post-id-56980Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56968#post-id-56968@Max Alekseyev can we use the Coppersmith method multivariate in this case?
(8*a*b-65*a-67*b+5) mod 319 = 0 ; (25*a+11)*(27*b+1) mod 1763 = 0Wed, 05 May 2021 10:44:37 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56968#post-id-56968Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56958#post-id-56958Does the polynomial have to be in this form to use bivariate Coppersmith method?
64*a^2*b^2-840*a^2*b+2600*a^2-856*a*b^2+10560*a*b-34800*a+2680*b^2-35472*b+108864=0Tue, 04 May 2021 22:50:59 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56958#post-id-56958Comment by P_1_6 for <p>I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.</p>
<p>As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that</p>
<pre><code>R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
</code></pre>
https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56952#post-id-56952- I understood the concept of the resultant [thank you]
- `(65-8 * b) * (67-8 * a) -1763 = 0` can the bivariable coppermith method be applied here?Tue, 04 May 2021 19:00:27 +0200https://ask.sagemath.org/question/56885/bivariate-coppersmith-method/?comment=56952#post-id-56952