mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2021-05-03, 10:34   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

5×97 Posts
Default 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
Alberico Lepore is offline   Reply With Quote
Old 2021-05-03, 18:39   #2
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

5×97 Posts
Default

N=p*q

with

p+q=8*x+4

Last fiddled with by Alberico Lepore on 2021-05-03 at 19:41
Alberico Lepore is offline   Reply With Quote
Old 2021-05-04, 09:32   #3
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1111001012 Posts
Default

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 ?
Alberico Lepore is offline   Reply With Quote
Old 2021-05-04, 21:25   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

5·97 Posts
Default

(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
Alberico Lepore is offline   Reply With Quote
Old 2021-05-05, 08:51   #5
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

7458 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2021-05-06, 21:26   #6
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

5·97 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
(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?
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trying to solve discriminant of a cubic polynomial by product method carpetpool Abstract Algebra & Algebraic Number Theory 6 2018-11-28 13:16
New factorization method henryzz Miscellaneous Math 4 2017-04-13 12:41
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
B1 and B2 in P-1 method Miszka Math 13 2013-12-27 20:23
New Method 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.