mersenneforum.org Letzte attempt to factor RSA
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-04, 16:34 #67 Alberico Lepore     May 2017 ITALY 46510 Posts 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 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 ?
2020-09-04, 17:16   #68
Alberico Lepore

May 2017
ITALY

3×5×31 Posts

Quote:
 Originally Posted by Alberico Lepore 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 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

2020-09-04, 17:49   #69
Alberico Lepore

May 2017
ITALY

1D116 Posts

Quote:
 Originally Posted by Alberico Lepore 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 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

 2020-09-05, 08:44 #70 Alberico Lepore     May 2017 ITALY 46510 Posts 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 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
 2020-09-05, 12:50 #71 Alberico Lepore     May 2017 ITALY 3×5×31 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 23 2020-05-20 09:51 Alberico Lepore Alberico Lepore 9 2020-05-01 09:41 jvang jvang 10 2019-02-03 23:17 jasong Programming 4 2005-11-29 22:24 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