mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-09-04, 16:34   #67
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

46510 Posts
Default

N=p*q , p=6*a+1=18*n+7 & q=6*b+1=18*m+1 and know that q/p<2

X=((4*N+1)/9+5)/8

ranges of A from 0 to H-1

solve (c*18-1)+(7*c+X-1)=(H*w+A)*(6*a+1) , c=5*(a+2)/3-3

Example

N=944871913984541047 -> X=52492884110252281

p=961749043 e q=982451629

we choose H=100 (I chose it at random and this is where I would need help)

solve (c*18-1)+(7*c+52492884110252281-1)=(100*w+53)*(6*a+1) , c=5*(a+2)/3-3

then

solve (c*18-1)+(7*c+52492884110252281-1)=(100*w-100*W+53)*(6*a+1), c=5*(a+2)/3-3 ,c,w

->

w=(157478652330756703 + 300*W + (1800*W-829)*a )/(300 + 1800*a)

from which

q=-(1800*W-829)=982451629

Since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-1800)=-540025
1374679536/(-1800)=-763711

then O(223686)

in fact for W=-545806

you will have

-(1800*W-829)=982451629

How do we optimize it?
What is the best choice of H if we know that q/p<2 ?
Alberico Lepore is offline   Reply With Quote
Old 2020-09-04, 17:16   #68
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×5×31 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
N=p*q , p=6*a+1=18*n+7 & q=6*b+1=18*m+1 and know that q/p<2

X=((4*N+1)/9+5)/8

ranges of A from 0 to H-1

solve (c*18-1)+(7*c+X-1)=(H*w+A)*(6*a+1) , c=5*(a+2)/3-3

Example

N=944871913984541047 -> X=52492884110252281

p=961749043 e q=982451629

we choose H=100 (I chose it at random and this is where I would need help)

solve (c*18-1)+(7*c+52492884110252281-1)=(100*w+53)*(6*a+1) , c=5*(a+2)/3-3

then

solve (c*18-1)+(7*c+52492884110252281-1)=(100*w-100*W+53)*(6*a+1), c=5*(a+2)/3-3 ,c,w

->

w=(157478652330756703 + 300*W + (1800*W-829)*a )/(300 + 1800*a)

from which

q=-(1800*W-829)=982451629

Since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-1800)=-540025
1374679536/(-1800)=-763711

then O(223686)

in fact for W=-545806

you will have

-(1800*W-829)=982451629

How do we optimize it?
What is the best choice of H if we know that q/p<2 ?

for H=1000

solve (c*18-1)+(7*c+52492884110252281-1)=(1000*w+1000*W+653)*(6*a+1) , c=5*(a+2)/3-3 , c,w


Since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-18000)=-54002
1374679536/(-18000)=-76371

18000*W+11629=982451629

W=54580

(54580-54002)*653=377434 cicles to find the solutions

(545806-540025)*53=306393 cicles to find the solutions in the first case


if we choose H = 10 ^ n

it can be deduced that it depends on the value of the first digit of A.

for example if I have 12345006789 the best case is H = 1000000

so the thing is very Random

you could try with values H! = 10 ^ n
Alberico Lepore is offline   Reply With Quote
Old 2020-09-04, 17:49   #69
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1D116 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
for H=1000

solve (c*18-1)+(7*c+52492884110252281-1)=(1000*w+1000*W+653)*(6*a+1) , c=5*(a+2)/3-3 , c,w


Since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-18000)=-54002
1374679536/(-18000)=-76371

18000*W+11629=982451629

W=54580

(54580-54002)*653=377434 cicles to find the solutions

(545806-540025)*53=306393 cicles to find the solutions in the first case


if we choose H = 10 ^ n

it can be deduced that it depends on the value of the first digit of A.

for example if I have 12345006789 the best case is H = 1000000

so the thing is very Random

you could try with values H! = 10 ^ n
in our case the hidden number is 54580653

so if we find a factor

example

54580653=3^2*263*23059



solve (c*18-1)+(7*c+52492884110252281-1)=(263*w+263*W+0)*(6*a+1) , c=5*(a+2)/3-3 , c,w


-(-4734*W+125)=q

Since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-4734)=-205332
1374679536/(-4734)=-290384

-(-4734*W+125)=982451629

W=207531

(207531-205332)*1=2199 cicles to find the solutions

but this is an exceptional case

however, we can go near to 0
Alberico Lepore is offline   Reply With Quote
Old 2020-09-05, 08:44   #70
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

46510 Posts
Default

I have optimized the math part of the algorithm a bit

solve (c*18-1)+(7*c+X-1)=(H*w+A)*(6*a+1) , (c*18-1)-(7*c+X-1)=(-K*y-B)*(6*a+1) , c=5*(a+2)/3-3

Example

N=944871913984541047 -> X=52492884110252281

p=961749043 e q=982451629

we choose H=100 e B=87

for A=53 and B=62

(c*18-1)+(7*c+52492884110252281-1)=(100*w+53)*(6*a+1) , (c*18-1)-(7*c+52492884110252281-1)=(-87*y-62)*(6*a+1) , c=5*(a+2)/3-3

therefore

100*w+53+(-87*y-62)-10=0 solving the Diophantine with the extended Euclidean algorithm

w=(87*t+55) and y=(100*t+63)

let's go replace


(c*18-1)+(7*c+52492884110252281-1)=(100*(87*t+55)+53)*(6*a+1) , (c*18-1)-(7*c+52492884110252281-1)=(-87*(100*t+63)-62)*(6*a+1) , c=5*(a+2)/3-3

threfore

(c*18-1)+(7*c+52492884110252281-1)=(8700*t+5553)*(6*a+1) , (c*18-1)-(7*c+52492884110252281-1)=(-8700*t-5543)*(6*a+1) , c=5*(a+2)/3-3

so we used 62*62 cicli =3844 < 5553 not bad


solve (c*18-1)+(7*c+52492884110252281-1)=(8700*t-8700*T+5553)*(6*a+1), c=5*(a+2)/3-3 ,c,t

->

w=.........

from which

q=-(156600*T-99829)=982451629

since q/p>2 -> sqrt(N)< q <sqrt(2*N)

-> 972045222< q<1374679536

972045222/(-156600)=-6207
1374679536/(-156600)=-8778

-(156600*T-99829)=982451629

W=(6273-6207)*62*62=253704 cicles to find the solutions

306393 cicles to find the solutions in the first case


we gained 1/6 of the time
Alberico Lepore is offline   Reply With Quote
Old 2020-09-05, 12:50   #71
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×5×31 Posts
Default

WOW

Observe

4)
a=3*n+1 ; m =3*k , X=54*k*n+21*k+n+1

5)
a=3*n+1 ; m =3*k+1 , X=54*k*n+21*k+19*n+8

6)
a=3*n+1 ; m =3*k+2 , X=54*k*n+21*k+37*n+15



4)
52492884110252281=54*k*n+21*k+n+1 , m =3*k , m+7=(8700*t+5553) , (18*n+7)*(18*m+1)=944871913984541047
8700*t-3*k+5546=0 NOT admit integer solution

5)
52492884110252281=54*k*n+21*k+19*n+8 , m =3*k+1 , m+7=(8700*t+5553) , (18*n+7)*(18*m+1)=944871913984541047

8700*t-3*k+5545=0 NOT admit integer solution

6)
52492884110252281=54*k*n+21*k+37*n+15 , m =3*k+2 , m+7=(8700*t+5553) , (18*n+7)*(18*m+1)=944871913984541047

2900*t-k+1848=0 solving the diophantine we obtain t=s-1 and k=2900*s-1052


(6273-6207)+62*62=3910 cicles to find the solutions

Last fiddled with by Alberico Lepore on 2020-09-05 at 12:54
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
yet another attempt to bring down RSA Alberico Lepore Alberico Lepore 23 2020-05-20 09:51
Another RSA breach attempt Alberico Lepore Alberico Lepore 9 2020-05-01 09:41
An Attempt at Financial Responsibility jvang jvang 10 2019-02-03 23:17
Idea about 10,000,000 digit attempt. jasong Programming 4 2005-11-29 22:24
Factorization attempt on 100^99+99^100 JHansen Factoring 34 2005-05-27 19:24

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

Thu Sep 24 02:20:41 UTC 2020 up 13 days, 23:31, 0 users, load averages: 1.37, 1.46, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.