Factorization solved for ever

Dec 2013
1,117
41
Hi everybody,

I'm still ill I did not go nowhere but I finalized the factorization problem with new approach.
You have to read all the thread to understand my algorithm.
Between fevers and headhache I succeeded finally.
Here you could read my big discovery :

projecteuler.net • View topic - Factorization of odd semi-prime numbers

I wish to publish it here.
Read it carefully please and now I have the proof.
I will write it as soon as I feel better.

Good reading for those who care.
 
Last edited by a moderator:

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Here's a quick implementation of your test:
Code:
fac(n)=my(N);while(1,N+=n;my(k=sqrtint(2*N),r=2*N-k^2,a=sqrtint(k),g1=gcd(n,a^2+r),g2=gcd(n,(a+1)^2+r));if((g1>1&&g1<n)||(g2>1&&g2<n),return(N/n)))
Rather than return a factor, it returns the number of steps to get to this factor.

Here's a quick test framework which finds the average number of steps to factor n-digit semiprimes pq with p <= q < 2p (the hard ones).
Code:
test(n)=my(s,t);forprime(p=sqrtint(10^(n-1)\2)+1,sqrtint(10^n),forprime(q=max(p,10^(n-1)\p),min(10^n\p,2*p),s+=fac(p*q);t++));[s,t]
For 3-digit numbers, it took about 3.4 steps on average to find a factor (~7 gcds, ~7 square roots, etc.). For 7-digit numbers it took about 272 steps. You conjectured that the method would always take less than 2*log(10) steps, but this clearly isn't right -- the average is almost 20 times larger even at this small size.

I think that what you've found is a variant of Hart's OLF algorithm. It gives good results when factors are very close together but isn't practical for large numbers.

I'm trying to find the average for 8-digit numbers but the algorithm is slow enough that it's taking prohibitively long. Ah, it finally finished, taking an average of 864 steps. Randomized testing of 12-digit semiprimes of the indicated form shows that they take an average of ~80,000 steps, growing at a factor > 3 per digit. This is approximately the same rate of growth as trial division, so maybe I was wrong in calling this an OLF variant because even it isn't that slow. Hart's method gets a heuristic factor ~2.15 and McKee's method is only ~1.78.

Testing even individual 15-digit numbers is challenging, but the three I tried took 3.86 million, 3.92 million, and 7.32 million steps, respectively.
 
  • Like
Reactions: 1 person
Dec 2013
1,117
41
Thanks.
Did you read all the thread?
You need only 2 steps to compute it directly.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Thanks.
Did you read all the thread?
Yes, I believe so. I implemented what seemed to be your final method, not your original one.

You need only 2 steps to compute it directly.
How's that? Would you show those two steps with a moderate-sized example, like 23999887836455503939?
 
  • Like
Reactions: 1 person
Dec 2013
1,117
41
More precisely which algo did you use?
Please can you just copy-paste the one you used?
The last one was direct hit I mean a direct access to p and q.
 
Dec 2013
1,117
41
I gave it in my post.

Would you show the two-step factorization of 23999887836455503939, please?
Is this one?

With the new algorithm any semiprime number could factorized almost directly.
Here is the new general algorithm to factorize odd semiprime numbers.

n=731

1. Enter n=731
2. Enter A=2n=1462
3. Compute k and r such as A=k^2+r where k^2 is the biggest square less than A. A=38^2+18
Hence k=38 and r=18
4. Compute k-r=38-18=20
5. 20 is of the form s(s+1) where s=4
4*5=20
if not of the form of s(s+1) then go the algo "non composite" number
6. Compute c1=s^2+r=5^2+18=16+18=34
7. Compute c2=(s+1)^2+r=25+18=43
8. Compute gcd(n,c1)=gcd(731,34)=17
9. Compute gcd(n,c2)=gcd(731,43)=43
10. Check 731=17*43 print the factors p=17 q=43 end

Now we have factorized a number which is composite = product of 2 consecutive elements of (k,18) class.

Algo "non composite"number :

Assume that k is < r we have to find an A=n*2m such as r < k
This the first problem to solve :
We try some numbers m such as r become < k
Or we find a general solution to this problem.
let A=2m*n with r<k
If k-r is not of the form s(s+1)

Example : n=129 A=2*129=258
k=16 r=2
r<k
k-r=16-2=14
14 is not of the s(s+1)

We have to find a square t^2 such as :
tk-t^2*r=s(s+1)

t=3

3*16-9*2=30

30 is of the s(s+1)=5*6

Hence 258*9=2322

We enter a new A = 258*9=2322 and we start at step 2

The number is now a composite one and we are sure of that hence :

After all the steps :
k=48 r=18

c1=5^2+18=43
c2=6^2+18=54

n=129=43*3 done
.....................................

A number is direct hit or not.
I mean either a number is COMPOSITE in its class (k,r) and it will be easy to be factorized.
Either it is not then we have to "tranform" it on COMPOSITE in another class.
It will be then easily factorized.
That is the core of my algorithm.
I did it SUCCESSFULLY with 5-6 digits numbers.
I do not know what are the hurdles if the size of n get bigger.
It is up to you to check it and tell me the problems ahead.
If no particular problem then the factorization is over.
Thank you
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Would you show it with 23999887836455503939, please? I don't trust small numbers, they are very unusual creatures.
 
Dec 2013
1,117
41
My algo worth nothing.
So good luck to all.