mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-07-30, 13:19   #12
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×132 Posts
Default

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++
}

Last fiddled with by Alberico Lepore on 2021-07-30 at 14:52 Reason: in log_2 search the point if the system admit solutions if you find it {
Alberico Lepore is online now   Reply With Quote
Old 2021-07-30, 16:11   #13
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×132 Posts
Default

(*) 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.
Alberico Lepore is online now   Reply With Quote
Old 2021-07-30, 17:55   #14
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×132 Posts
Default

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++
}





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
Alberico Lepore is online now   Reply With Quote
Old 2021-07-31, 10:20   #15
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1FB16 Posts
Default

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


159757809<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 capofila

789*distance from the capofila
Alberico Lepore is online now   Reply With Quote
Old 2021-08-01, 13:48   #16
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·132 Posts
Default

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
Alberico Lepore is online now   Reply With Quote
Old 2021-08-02, 08:41   #17
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×132 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post

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

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]
Alberico Lepore is online now   Reply With Quote
Old 2021-10-25, 09:57   #18
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

50710 Posts
Default

In search of RSA factorization

Link Language [MATHS & ITA]
https://www.linkedin.com/pulse/alla-...berico-lepore/
Alberico Lepore is online now   Reply With Quote
Old 2021-10-25, 14:27   #19
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·132 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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 .....
Alberico Lepore is online now   Reply With Quote
Old 2021-10-26, 08:35   #20
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·132 Posts
Default

#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à?
Alberico Lepore is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lepore Factorization nr.88 Alberico Lepore Alberico Lepore 3 2021-07-13 14:43
Last factorization of Lepore in O(1) Alberico Lepore Alberico Lepore 2 2019-12-02 08:37
20th Test of primality and factorization of Lepore with Pythagorean triples Alberico Lepore Alberico Lepore 43 2018-01-17 15:55
14° Primality test and factorization of Lepore ( conjecture ) Alberico Lepore Alberico Lepore 48 2017-12-30 09:43
Lepore Factorization in O(k) Conjecture Alberico Lepore Alberico Lepore 61 2017-09-23 21:52

All times are UTC. The time now is 14:22.


Tue Oct 26 14:22:05 UTC 2021 up 95 days, 8:51, 0 users, load averages: 1.70, 1.39, 1.36

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.