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.Fri, 30 Apr 2021 19:21:39 +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 ?P_1_6Fri, 30 Apr 2021 19:21:39 +0200https://ask.sagemath.org/question/56885/Finding Small Roots of Multivariate Polynomial Modulo an Integerhttps://ask.sagemath.org/question/38135/finding-small-roots-of-multivariate-polynomial-modulo-an-integer/I am trying to apply Coppersmith's attack to find small roots of an example polynomial
$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$
For univariate polynomials, Coppersmith's attack is implemented via the `.small_roots()` function. However, it is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. Is there any workaround code / method that will allow for small root finding of the above polynomial, and others of the same form?
In this example, the results should be $x = 2$ and $y = 8$.
Relevant papers:
http://honors.cs.umd.edu/reports/lowexprsa.pdf
http://www.jscoron.fr/publications/bivariate.pdf
Thanks, and your time and effort are greatly appreciated.SanguiniusFri, 30 Jun 2017 05:30:13 +0200https://ask.sagemath.org/question/38135/Finding Small Roots of Multivariate Polynomials Modulo an Integerhttps://ask.sagemath.org/question/38134/finding-small-roots-of-multivariate-polynomials-modulo-an-integer/I am trying to apply Coppersmith's attack to find small roots of an example polynomial
$f(x,y) = (8x+7)(8y+7) \pmod{8}$
It is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage. However, is there a workaround code / method that will allow for small root finding of the above polynomial, and others of the same form?
Thanks, and your time and effort are greatly appreciated.
SanguiniusFri, 30 Jun 2017 05:28:46 +0200https://ask.sagemath.org/question/38134/