mersenneforum.org Lepore factorization nr. 105 (Bruteforce)
 Register FAQ Search Today's Posts Mark Forums Read

 2021-07-30, 13:19 #12 Alberico Lepore     May 2017 ITALY 22·127 Posts range ok h >=1 I tried to write the pseudo code Code: i=0 while(i<10) { solve this system and memorize y(i) and r(i) sqrt(N/((10+i)/10))=a , ((10+i)/10*a+a-4)/8=x , 2*x*(x+1)-y*(y-1)/2=(N-3)/8 , (sqrt(32*x+1)+1)/2=b , b*(b-1)/2-(sqrt(32*(x-b)+1)+1)/2*[(sqrt(32*(x-b)+1)+1)/2-1]/2=r } j=0 while (!(N mod p ==0 && p!=1 && p!=N)){ i=0 while(i<10) { solve this system with unique integer solution of h 2*(h)*(h-1)<(N-3)/8+k*(k-1)/2<=2*(h)*(h+1) , 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 , x-(sqrt(32*x+1)+1)/2
 2021-07-30, 16:11 #13 Alberico Lepore     May 2017 ITALY 1FC16 Posts (*) here I have to improve, multiplying the range by 10 ^ (tot), but I still don't know tot Last fiddled with by Uncwilly on 2021-07-30 at 21:37 Reason: Removed unneeded self quote of immediately preceding post.
 2021-07-30, 17:55 #14 Alberico Lepore     May 2017 ITALY 22·127 Posts Code: i=0 while(i<10) { solve this system and memorize y(i) and r(i) sqrt(N/((10+i)/10))=a , ((10+i)/10*a+a-4)/8=x , 2*x*(x+1)-y*(y-1)/2=(N-3)/8 , (sqrt(32*x+1)+1)/2=b , [b*(b-1)/2-(sqrt(32*(x-b)+1)+1)/2*[(sqrt(32*(x-b)+1)+1)/2-1]/2]/2=r } j=0 while (!(N mod p ==0 && p!=1 && p!=N)){ i=0 while(i<10) { solve this system with unique integer solution of h 2*(h)*(h-1)<(N-3)/8+k*(k-1)/2<=2*(h)*(h+1) , 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 , x-(sqrt(32*x+1)+1)/2[range of x]>=1 if exist (*) if exist { choose the only possible integer solution of x x-(sqrt(32*x+1)+1)/2=h 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 calculate p p=4*x+1-2*(y-1) } i++ } j++ } Example N=390644893234047643 , sqrt(N/(15/10))=a , (15/10*a+a-4)/8=x , 2*x*(x+1)-y*(y-1)/2=(N-3)/8 , (sqrt(32*x+1)+1)/2=b , [b*(b-1)/2-(sqrt(32*(x-b)+1)+1)/2*[(sqrt(32*(x-b)+1)+1)/2-1]/2]/2=r r=71437,..... N=390644893234047643 , 2*(h)*(h-1)<(N-3)/8+k*(k-1)/2<=2*(h)*(h+1) , 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 , x-(sqrt(32*x+1)+1)/2= 1 & <2
 2021-07-31, 10:20 #15 Alberico Lepore     May 2017 ITALY 1111111002 Posts If we establish how far x can be from the capofila at mos (order size)t, here r=71501 , r=(2*h+sqrt(32*h+81)+9)/2-(2*h-sqrt(32*h+49)+7)/2 , (2*x-sqrt(32*x+1)-1)/2
 2021-08-01, 13:48 #16 Alberico Lepore     May 2017 ITALY 22×127 Posts Code: check=0 i=0 while(i<10) { solve this system sqrt(N/((10+i)/10))=a , ((10+i)/10*a+a-4)/8=x , 2*x*(x+1)-b*(b-1)/2=(N-3)/8 } memorize b(i) C=0 while (check==0){ i=0 while(i<10 && check==0) { h=x-b(i)/2-C // b/2 must be integer , [2*(h-1)*(h-1+1)] < N-3)/8-b(i)/2*(4*x+1-2*(y-1)) <= [2*h*(h+1)] , 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 while(min_h <= max_h && check==0){ x=h+b/2+C 2*(x)*(x+1)-y*(y-1)/2=(N-3)/8 calculate p p=4*x+1-2*(y-1) if(N mod p ==0 && p!=1 && p!=N){ check=1 break } min_h++ } i++ } C++ }` Example N=390644893234047643 , sqrt(N/(15/10))=a , (15/10*a+a-4)/8=x , 2*x*(x+1)-b*(b-1)/2=(N-3)/8 b = 63790420 h=x-(63790420)/2-C , [2*(h-1)*(h-1+1)] < (390644893234047643-3)/8-(63790420)/2*(4*x+1-2*(y-1)) <= [2*h*(h+1)] , 2*(x)*(x+1)-y*(y-1)/2=(390644893234047643-3)/8 per C=-7454 127855236<=h<127855255 -> size range = 19 per h=127855241 , h=x-(63790420)/2-7454 -> x=159757905 the problem is that size range of h is decreasing for C=0 127580838<=h<127584034 -> size range = 3196 for C=3727 127775161<=h<127775188 -> size range =27 an exponential decrease would seem to our advantage ********************************************************************* UPDATE: I tried to solve in x and I noticed that the first valid value is our x = 159757905 if it would always happen the cost of factoring 390644893234047643 would be 7454 * 10 = 74540 Tomorrow morning I will continue with other tests https://www.wolframalpha.com/input/?...%2F8+%2Ch+%2Cy Last fiddled with by Alberico Lepore on 2021-08-01 at 19:00 Reason: UPDATE
2021-08-02, 08:41   #17
Alberico Lepore

May 2017
ITALY

22×127 Posts

Quote:
 Originally Posted by Alberico Lepore ********************************************************************* UPDATE: I tried to solve in x and I noticed that the first valid value is our x = 159757905 if it would always happen the cost of factoring 390644893234047643 would be 7454 * 10 = 74540 Tomorrow morning I will continue with other tests https://www.wolframalpha.com/input/?...%2F8+%2Ch+%2Cy
unfortunately this is not true.

But x is very close to min_range_x

I tested on a number of 30 digits with p and q of 15 digits and the result is 37

N=188723059539473758658629052963

N=188723059539473758658629052963
,
sqrt(N/(18/10))=a
,
(18/10*a+a-4)/8=x
,
2*x*(x+1)-b*(b-1)/2=(N-3)/8

b=64759908643727

h=x-(64759908643726)/2-88973930
,
[2*(h-1)*(h-1+1)]
<
(188723059539473758658629052963-3)/8-(64759908643726)/2*(4*x+1-2*(y-1))
<=
[2*h*(h+1)]
,
2*(x)*(x+1)-y*(y-1)/2=(188723059539473758658629052963-3)/8

range x 113364197263548<=x<=113364197263741

size_range 193

distance x 37

x=113364197263585

I need to be able to quantify distance x or size_range_x

total cost [10*my_quantify *88973930] about N ^ (1/3)

It's still a very heavy bruteforce, but I'm happy

Last fiddled with by Alberico Lepore on 2021-08-02 at 08:50 Reason: [10*my_quantify *88973930]

 2021-10-25, 09:57 #18 Alberico Lepore     May 2017 ITALY 1FC16 Posts In search of RSA factorization Link Language [MATHS & ITA] https://www.linkedin.com/pulse/alla-...berico-lepore/
2021-10-25, 14:27   #19
Alberico Lepore

May 2017
ITALY

22·127 Posts

Quote:
 Originally Posted by Alberico Lepore In search of RSA factorization Link Language [MATHS & ITA] https://www.linkedin.com/pulse/alla-...berico-lepore/
For sure [IF everything is correct] I would not choose a semi-prime RSA in the form N = 4 * ((2 ^ k) * w) +3 for a suitable k and more .....

 2021-10-26, 08:35 #20 Alberico Lepore     May 2017 ITALY 22×127 Posts #aiuto su #TeoriaDeiNumeri Gentilmente qualcuno mi aiuterebbe su Teoria dei Numeri ? tutte le variabili che nominerò sono interi [Aiuto1] E' vero che tutti i numeri nella forma N=4*((2^k)*w)+3 si possono esprimere in questa forma ? 4*((2^k)*x+1)^2-(2*((2^(k))*y)-1)^2 [Aiuto2] E' vero che per trasformare un qualsiasi numero dispari in un numero nella forma N=4*((2^k)*w)+3 per un k scelto si proceda in questo modo ? se N-3 mod 2^(i+1) è diverso da 0 moltiplichi per N per 2^i+1 con i che parte da 1 ed arriva a k+1 [Aiuto3] Questa relazione 4*((2^k)*x+1)^2>=4*((2^k)*x+1)^2-(2*((2^(k))*y)-1)^2>4*((2^k)*(x-1)+1)^2 ci dice quanto deve essere piccola y rispetto ad x conoscendo k Si potrebbe creare un algoritmo di fattorizzazione che per ogni step di i+1 del secondo aiuto [Aiuto2] se y verifica quella disequazione e si trova in O(1) il valore di x e quindi 2 fattori P e Q taliche P=p*s e Q=q*t dove p e q sono i fattori del numero dispari iniziale e quindi facendo massimo comun divisore tra il numero iniziale e P o Q troveremmo p e q il tutto aumentando i di un unità ad ogni step fino ad un k che ci riveli la fattorizzazione p*q ? [Aiuto4] Termina sicuramente l'algoritmo creato? Qual è la complessità computazionale per fattorizzare un numero dispari N=p*q ? E' forse casuale questa complessità?
 2021-10-28, 07:53 #21 Alberico Lepore     May 2017 ITALY 1FC16 Posts Pseudo-code & Explanation [ITA] https://www.matematicamente.it/forum...13821#p8513821

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 3 2021-07-13 14:43 Alberico Lepore Alberico Lepore 2 2019-12-02 08:37 Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 Alberico Lepore Alberico Lepore 61 2017-09-23 21:52

All times are UTC. The time now is 12:27.

Fri Dec 3 12:27:44 UTC 2021 up 133 days, 6:56, 0 users, load averages: 1.08, 1.10, 1.00