 mersenneforum.org Is it possible to use The Jubjub bird and The frumious Bandersnatch method in this polynomial?
 Register FAQ Search Today's Posts Mark Forums Read 2021-05-03, 10:34 #1 Alberico Lepore   May 2017 ITALY 2×32×29 Posts Is it possible to use The Jubjub bird and The frumious Bandersnatch method in this polynomial? 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 ************************************************************************************************ OTHER INFORMATION ************************************************************************************ You can choose some coefficients and their size order of this type of polynomial in O (16). really is O(8) (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   2021-05-03, 18:39 #2 Alberico Lepore   May 2017 ITALY 2·32·29 Posts N=p*q with p+q=8*x+4 Last fiddled with by Alberico Lepore on 2021-05-03 at 19:41   2021-05-04, 09:32 #3 Alberico Lepore   May 2017 ITALY 2·32·29 Posts 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| 2021-05-04, 21:25 #4 Alberico Lepore   May 2017 ITALY 2·32·29 Posts (65-8 * b) * (67-8 * a) -1763 = 0 -> (8*a*b-65*a-67*b+324)=0 which is irreducible pag 3 http://www.crypto-uni.lu/jscoron/pub.../bivariate.pdf   2021-05-05, 08:51 #5 Alberico Lepore   May 2017 ITALY 2·32·29 Posts 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 = 0   2021-05-06, 21:26   #6
Alberico Lepore

May 2017
ITALY

52210 Posts Quote:
 Originally Posted by Alberico Lepore (65-8 * b) * (67-8 * a) -1763 = 0 -> (8*a*b-65*a-67*b+324)=0 which is irreducible pag 3 http://www.crypto-uni.lu/jscoron/pub.../bivariate.pdf
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?  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 6 2018-11-28 13:16 henryzz Miscellaneous Math 4 2017-04-13 12:41 carpetpool Miscellaneous Math 14 2017-02-18 19:46 Miszka Math 13 2013-12-27 20:23 Unregistered Miscellaneous Math 14 2013-05-24 10:55

All times are UTC. The time now is 02:11.

Mon Aug 8 02:11:44 UTC 2022 up 31 days, 20:59, 1 user, load averages: 1.01, 1.22, 1.16