Ask Your Question

P_1_6's profile - activity

2023-12-10 18:23:43 +0100 received badge  Famous Question (source)
2023-05-19 21:57:24 +0100 received badge  Popular Question (source)
2022-12-30 14:00:33 +0100 received badge  Popular Question (source)
2022-11-30 00:06:08 +0100 received badge  Famous Question (source)
2022-05-29 20:58:00 +0100 received badge  Notable Question (source)
2022-02-04 05:57:42 +0100 received badge  Famous Question (source)
2021-08-31 03:11:28 +0100 received badge  Popular Question (source)
2021-05-15 21:25:39 +0100 received badge  Popular Question (source)
2021-05-13 13:23:06 +0100 edited question Reduction of the coefficients of a polynomial using the LLL algorithm

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

2021-05-13 13:00:16 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-13 12:56:59 +0100 asked a question Reduction of the coefficients of a polynomial using the LLL algorithm

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

2021-05-12 21:12:03 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-12 10:56:46 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 19:39:03 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 18:27:28 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 16:55:29 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 12:44:18 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 12:19:59 +0100 marked best answer 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)
2021-05-11 12:13:18 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 12:09:32 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-11 09:28:00 +0100 received badge  Enthusiast
2021-05-10 18:33:01 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-10 12:31:35 +0100 commented answer Reduction of the coefficients of a polynomial in sage

@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

2021-05-10 12:24:36 +0100 commented answer Reduction of the coefficients of a polynomial in sage

@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

2021-05-10 12:24:07 +0100 commented answer Reduction of the coefficients of a polynomial in sage

@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

2021-05-10 12:23:47 +0100 commented answer Reduction of the coefficients of a polynomial in sage

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

2021-05-10 10:15:24 +0100 commented answer Reduction of the coefficients of a polynomial in sage

thank you mnTSW

2021-05-10 09:59:16 +0100 commented answer Reduction of the coefficients of a polynomial in sage

thank you mnTSV

2021-05-08 15:17:35 +0100 commented answer Bivariate Coppersmith method

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

2021-05-08 15:16:15 +0100 asked a question 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

2021-05-07 16:16:00 +0100 commented answer Bivariate Coppersmith method

@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

2021-05-07 16:09:28 +0100 commented answer Bivariate Coppersmith method

@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

2021-05-07 11:55:34 +0100 commented answer Bivariate Coppersmith method

@Max Alekseyev thanks for your patience

2021-05-07 11:52:46 +0100 commented answer Bivariate Coppersmith method

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

2021-05-07 11:47:33 +0100 received badge  Notable Question (source)
2021-05-06 18:10:04 +0100 commented answer Bivariate Coppersmith method

@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

2021-05-06 18:08:58 +0100 marked best answer 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 ?