Lepore factorization nr. 105 (Bruteforce)
 

[url]https://www.academia.edu/49978974/Lepore_factorization_nr_105_Bruteforce[/url]

What do you think?

ERRATA CORRIGE

[2*(x-1)*((x-1)+1)] < [2*x*(x+1)-y*(y-1)/2] <= [2*(x)*(x+1)]

1 <= y < (sqrt(32*x+1)+1)/2

[CODE]
/*
This algorithm is generic and does not exploit that q / p < 2

Plus it uses a single A and not many A
*/


A=9+16*a;//choose A with many small factors

if(M % 4 ==1){
M=3*M;
}
if((M % 8 == 3){
N=M;
}else{
N=5*M;
}
while(1){
if([1/4*(sqrt(N+1)+2)] != (int)[1/4*(sqrt(N+1)+2)]){
x=(int)[1/4*(sqrt(N+1)+2)];
}else{
x=[1/4*(sqrt(N+1)+2)]-1;
}


P=4*x+2-sqrt[4*(2*x+1)^2-N];
Q=N/P;
if (P is integer && (P % M) !=0 && (Q % M) !=0){
breack;
}
N=N*A
}
p=GCD(P,M);


[/CODE]

I tried to implement it without good results

[url]https://github.com/Piunosei/Lepore-factorization-nr.-105-Bruteforce-/blob/main/lepore_105.c[/url]

the new theory applied to Lepore Factorization nr. 105
If the theory is correct to factor RSA with q / p <2 it would seem O ((log_2 (n)) ^ 2) but I am studying how to implement it in O (2 * (log_2 (n))),after lunch I will study this third hypothesis and the implementation tonight

Hello

Unfortunately
O((log_2(n))^2) does not work
O(2*(log_2(n))) does not work
It would seem that O(K*[sqrt(8*sqrt(n)-31)-1]/16) work
K depends on the number n

I still don't know the order of size of K
for example for n=390644893234047643 -> K=4

with a parallel distribution on many computers, finding p and q takes as long as possible
Example on 10 computers for n = 390644893234047643 would take 16150 cycles or 1615 for each computer

use m not 2*m here [url]https://www.academia.edu/50318218/Crypto_factorization_example[/url]

15 digit 3194383
12 digit 63245
9 digit 3195


p= 9 digit

[2*(h-1)*((h-1)+1)]
<
[2500000062500000-1/2 (h - x) (-1 + h - x + 2 y)+2 (h - x) (1 + h + x)]
<=
[2*(h)*(h+1)]
,
2*(x)*(x+1)-y*(y-1)/2=2500000062500000
,
h=62500001

37500000<=x<37503195 -> 3195

p=12 digit

[2*(h-1)*((h-1)+1)]
<
[2500000000062500000000-1/2 (h - x) (-1 + h - x + 2 y)+2 (h - x) (1 + h + x)]
<=
[2*(h)*(h+1)]
,
2*(x)*(x+1)-y*(y-1)/2=2500000000062500000000
,
h=12500000000

37500000000<=<<37500063245 -> 63245

P=15 digit

[2*(h-1)*((h-1)+1)]
<
[2500000000000062500000000000-1/2 (h - x) (-1 + h - x + 2 y)+2 (h - x) (1 + h + x)]
<=
[2*(h)*(h+1)]
,
2*(x)*(x+1)-y*(y-1)/2=2500000000000062500000000000
,
h=62500000000001

37500000000000<=x<37500003194383 -> 3194383

@CRGreathouse I know you don't talk to me anymore but I have achieved an extraordinary result with your number

N=390644893234047643

sqrt(390644893234047643/(15/10))=a
,
(15/10*a+a-4)/8=x
,
2*x*(x+1)-y*(y-1)/2=(390644893234047643-3)/8

->

y=63790420,........




[2*(h)*(h-1)]
<
[(390644893234047643-3)/8+k*(k-1)/2]
<=
[2*(h)*(h+1)]
,
2*(x)*(x+1)-y*(y-1)/2=(390644893234047643-3)/8
,
x-(sqrt(32*x+1)+1)/2 <h<x+(sqrt(32*x+1)+1)/2
,
k=63790420+j*100000

for j=25

see please range h here

[url]https://www.wolframalpha.com/input/?i=%5B2*%28h%29*%28h-1%29%5D++%3C+++%5B%28390644893234047643-3%29%2F8%2Bk*%28k-1%29%2F2%5D+++%3C%3D+++%5B2*%28h%29*%28h%2B1%29%5D++%2C++2*%28x%29*%28x%2B1%29-y*%28y-1%29%2F2%3D%28390644893234047643-3%29%2F8++%2C+x-%28sqrt%2832*x%2B1%29%2B1%29%2F2+%3Ch%3Cx%2B%28sqrt%2832*x%2B1%29%2B1%29%2F2%2Ck%3D63790420%2Bj*100000%2Cj%3D25[/url]

total cost for factorize N=390644893234047643 is 25*10=250 step

[QUOTE=VBCurtis;584367]I don't think you count steps very well.

Consider trial factoring. Each prime tried is a single step, and a bunch of them don't work. If you find one that does, the number of steps to find that factor is the number of TOTAL trials, including all the things that didn't work.

Your "method" appears to be such a thing- try a bunch of parameter selections until something works, and then claim "it only took 250 steps!". How many parameters did you try against this number that took thousands of steps, or didn't work at all? That's the actual "number of steps" you took to factor it.[/QUOTE]





yes, I'll try to explain myself better

knowing that the ratio q / p <2 then I will test:


q / p
>

1


1.1


1.2


1.3


1.4


1.5


1.6


1.7


1.8


1.9


and I will execute them at the same time

so it will be the actual time for 10

we consider a 30-digit number with p and q also not prime numbers

188723059539473758658629052963=323456789054341*583456789054343

q/p=1,8038167965499768547404880957269



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


N=188723059539473758658629052963
,
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<h<x+(sqrt(32*x+1)+1)/2
,
k=64759908643727+2399*[COLOR="Red"]100000000[/COLOR]

I still can't establish the exact size order of the number in red, it would appear from the first tests to be
10 ^ [((digit p) +1) / 2]
, but I'm still studying this number.

In theory, if the above were confirmed,
since k <= y <p with y being the order size of p-1 and the first digit of y is given by the 10 ratios we will have our solution in
10 * {[[ digit p] -1] -1 - [((digit p) +1) / 2]}

I repeat still do not know well the number in red.

maybe i quantified the r number in red

red value = r

N=188723059539473758658629052963
,
sqrt(N/(18/10))=a
,
(18/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

r=120441770,......


N=188723059539473758658629052963
,
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<h<x+(sqrt(32*x+1)+1)/2
,
k=64759908643727+1992*120441770

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<h<x+(sqrt(32*x+1)+1)/2
,
k=y(i)+j*r(i)

in the range [y(i)+(j-1)*r(i),y(i)+j*r(i)] in log_2 search the point if the system admit solutions

if you find it {

x-(sqrt(32*x+1)+1)/2=h

aproximate x to integer

2*(x)*(x+1)-y*(y-1)/2=(N-3)/8

calculate p

p=4*x+1-2*(y-1)
}
i++
}

j++
}[/CODE]

(*) here I have to improve, multiplying the range by 10 ^ (tot), but I still don't know tot

[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<h<x+(sqrt(32*x+1)+1)/2
,
k=y(i)+j*r(i)

in the range [y(i)+(j-2)*r(i),y(i)+j*r(i)] in log_2 search 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++
}[/CODE]






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<h<x+(sqrt(32*x+1)+1)/2
,
k=63790420+j*71437

suppose we have arrived at j =34




k in the range [63790420+32*71437;63790420+34*71437]

with biinarie research find x=159757905

for k=66207577

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<h<x+(sqrt(32*x+1)+1)/2
,
k=66207577

infatti range x (159757904,46492;159757905,46503)

range size >= 1 & <2

If we establish how far x can be from the [COLOR="Red"]capofila[/COLOR] 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<h<(2*x+sqrt(32*x+1)+1)/2


[COLOR="red"]159757809[/COLOR]<x<159793564

in this case 95


we will establish the maximum time



N=390644893234047643 , sqrt(N)=a , (a+a-4)/8=x , (sqrt(32*x+1)+1)/2=b/2

b=70712

(71501-70712)*distance from the [COLOR="red"]capofila[/COLOR]

789*distance from the [COLOR="red"]capofila[/COLOR]

[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++
}[/CODE]




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

[url]https://www.wolframalpha.com/input/?i=solve+h%3Dx-%2863790420%29%2F2-7454+%2C+%5B2*%28h-1%29*%28h-1%2B1%29%5D+++%3C++%28390644893234047643-3%29%2F8-%2863790420%29%2F2*%284*x%2B1-2*%28y-1%29%29++%3C%3D+++%5B2*h*%28h%2B1%29%5D++%2C+++2*%28x%29*%28x%2B1%29-y*%28y-1%29%2F2%3D%28390644893234047643-3%29%2F8+%2Ch+%2Cy[/url]

[QUOTE=Alberico Lepore;584549]

*********************************************************************

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

[url]https://www.wolframalpha.com/input/?i=solve+h%3Dx-%2863790420%29%2F2-7454+%2C+%5B2*%28h-1%29*%28h-1%2B1%29%5D+++%3C++%28390644893234047643-3%29%2F8-%2863790420%29%2F2*%284*x%2B1-2*%28y-1%29%29++%3C%3D+++%5B2*h*%28h%2B1%29%5D++%2C+++2*%28x%29*%28x%2B1%29-y*%28y-1%29%2F2%3D%28390644893234047643-3%29%2F8+%2Ch+%2Cy[/url][/QUOTE]

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

In search of RSA factorization

Link Language [MATHS & ITA]
[URL="https://www.linkedin.com/pulse/alla-ricerca-della-fattorizzazione-rsa-alberico-lepore/"]https://www.linkedin.com/pulse/alla-ricerca-della-fattorizzazione-rsa-alberico-lepore/[/URL]

[QUOTE=Alberico Lepore;591559]In search of RSA factorization

Link Language [MATHS & ITA]
[URL="https://www.linkedin.com/pulse/alla-ricerca-della-fattorizzazione-rsa-alberico-lepore/"]https://www.linkedin.com/pulse/alla-ricerca-della-fattorizzazione-rsa-alberico-lepore/[/URL][/QUOTE]

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

#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à?

Pseudo-code
&
Explanation [ITA]

[url]https://www.matematicamente.it/forum/viewtopic.php?f=26&t=215668&p=8513821#p8513821[/url]