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 Apr 2023 07:06:42 +0200Find a root of bivariate polynomialhttps://ask.sagemath.org/question/67401/find-a-root-of-bivariate-polynomial/Given a bivariate and symmetric polynomial $P(x,y)$ with a high degree (probably larger than 8). Is there any algorithm that helps me know if $P(x,y)$ has a root over $\mathbb{R}^+$ or not? I may not need a specific root, I just want to check if there is a root, or not.
*P/S: I'm new to SageMath. Currently, I know some basic operation with multivariate polynomial like factorizing, adding, substracting, ... two polynomials. It would be great if you can explain your answer a little bit. Thank you.toranSat, 08 Apr 2023 07:06:42 +0200https://ask.sagemath.org/question/67401/Bivariate 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/