mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-07-16, 13:03   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default Lepore factorization nr. 105 (Bruteforce)

https://www.academia.edu/49978974/Le...105_Bruteforce

What do you think?
Alberico Lepore is offline   Reply With Quote
Old 2021-07-17, 07:20   #2
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2021-07-17, 19:29   #3
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

50810 Posts
Default

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);

Last fiddled with by Alberico Lepore on 2021-07-17 at 19:37 Reason: }
Alberico Lepore is offline   Reply With Quote
Old 2021-07-20, 12:15   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22×127 Posts
Default

I tried to implement it without good results

https://github.com/Piunosei/Lepore-f...n/lepore_105.c
Alberico Lepore is offline   Reply With Quote
Old 2021-07-22, 11:25   #5
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2021-07-24, 21:10   #6
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

50810 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2021-07-25, 10:14   #7
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22×127 Posts
Default

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

Last fiddled with by Uncwilly on 2021-07-30 at 21:36 Reason: Removed unneeded self quote of immediately preceding post.
Alberico Lepore is offline   Reply With Quote
Old 2021-07-28, 20:02   #8
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default

use m not 2*m here https://www.academia.edu/50318218/Cr...zation_example

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
Alberico Lepore is offline   Reply With Quote
Old 2021-07-29, 19:25   #9
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22×127 Posts
Default

@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

https://www.wolframalpha.com/input/?...00000%2Cj%3D25

total cost for factorize N=390644893234047643 is 25*10=250 step
Alberico Lepore is offline   Reply With Quote
Old 2021-07-30, 09:10   #10
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22×127 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.




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*100000000

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.
Alberico Lepore is offline   Reply With Quote
Old 2021-07-30, 11:01   #11
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

50810 Posts
Default

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

Last fiddled with by Uncwilly on 2021-07-30 at 21:37 Reason: Removed unneeded self quote of immediately preceding post.
Alberico Lepore is offline   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 23:45.


Sun Nov 28 23:45:53 UTC 2021 up 128 days, 18:14, 0 users, load averages: 2.12, 1.65, 1.39

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.