mersenneforum.org Is it possible to use The Jubjub bird and The frumious Bandersnatch method in this polynomial?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-05-03, 10:34 #1 Alberico Lepore     May 2017 ITALY 5×97 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 5×97 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 1111001012 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 5·97 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 7458 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

5·97 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

 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:47.

Sat May 15 02:47:32 UTC 2021 up 36 days, 21:28, 0 users, load averages: 1.39, 1.83, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}