P_1_6's profile - activity

Reduction of the coefficients of a polynomial using the LLL algorithm Given the two polynomials in two variables x and y

@Max Alekseyev I asked here https://ask.sagemath.org/question/57105/reduction-of-the-coefficients-of-a-polynomial-using-

Reduction of the coefficients of a polynomial using the LLL algorithm Given the two polynomials in two variables x and y

@Max Alekseyev thank you. It will take years to implement but I will make it. I am a beginner.

@Max Alekseyev in the wikipedia you showed me, in the "Implementations" section it says that it is implemented in sage "

@Max Alekseyev I posted a free paper for you right now here https://mersenneforum.org/showthread.php?p=578212#post578212

@Max Alekseyev Thanks for everything. One last question, if possible: What is the computational cost of using LLL to fi

@Max Alekseyev What is the computational complexity over j and N? Maybe that's my problem. My computer does not output

@Max Alekseyev for j = 100 Where am I wrong? from sage.modules.free_module_integer import IntegerLattice def mnTSW(N,a

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)

@Max Alekseyev for j = 100 Where am I wrong? from sage.modules.free_module_integer import IntegerLattice def mnTSW(N,a

@Max Alekseyev for j = 100 Where am I wrong? from sage.modules.free_module_integer import IntegerLattice def mnTSW(N,a

@Max Alekseyev and if you wanted 64 <T <64 * j where j is an integer greater than 1 and 0< S <= sqrt(N) an

@Max Alekseyev and if you wanted 64 <T <64 * j where j is an integer greater than 1 and S> 0 and W> 0 How

@Max Alekseyev and if you wanted 64 <T <64 * t where t is an integer greater than 1 and S> 0 and W> 0 How

@Max Alekseyev and if you wanted 64 <T <64 * t where t is an integer greater than 1 and T> 0 and W> 0 How

Max Alekseyev and if you wanted 64 <t &lt;64="" *="" t="" where="" t="" is="" an="" integer="" greater="" than="

thank you mnTSW

thank you mnTSV

@Max Alekseyev https://ask.sagemath.org/question/57023/reduction-of-the-coefficients-of-a-polynomial-in-sage/

Reduction of the coefficients of a polynomial in sage Given the two polynomials in two variables x and y A(y,x)=((a1)*y

@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

@Max Alekseyev Given the two polynomials in two variables x and y A(y,x)=((a1)*y+(a2))*(27*(a3)+(a4)) B(y,x)=((b4)-(b

@Max Alekseyev thanks for your patience

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 ?

@Max Alekseyev thanks for your patience, could you kindly take a look R.<a,b> = PolynomialRing(ZZ) p = (25*a+11)*

@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 c