20061105, 23:58  #1 
Nov 2006
Singapore
3×5^{2} Posts 
A new prime factoring algorithm?
Hi would appreciate any feedback on this method I've developed. I've also attached a pdf for those who wish to look at it in their own time.I've been unable to test it out since I am not a programmer but I think the math is sound.
Best Regards Visu If the number to be factored is N, express it in the form (a12 + a22 +...+ an2) – (b12 + b22 +...+ bn2 ) This can be done by the following procedure a12 – N = k1 (where a1 is the next integer > (N)1/2 ) b12 – k1 = k2 and so on until kn = 0 Now [(a12 + a22 +...+ an2) + k ] = A2 and [(b12 + b22 +...+ bn2 ) + k] = B2  (1) where N = A2 – B2 one value of A and B is given by A = ((N+1)/2) and B = ((N1)/2) and for prime numbers this is the only way to express N as a difference of two squares and hence there will only be one value of k which can be easily found . We will refer to this as k1 . For odd composite numbers there will be other values of k satisfying the equation corresponding to the number of factors they have. We now obtain a binary quadratic equation corresponding to N using the above information. We do this as follows: (a1 + 1)2 – (a12 + a22 +...+ an2) =d1 (a1 + 2)2 – (a12 + a22 +...+ an2) =d2 (a1 + 3)2 – (a12 + a22 +...+ an2) =d3 and likewise for b to get e1, e2 and e3. Next using calculus of finite difference we obtain d1 d2 d3 d4 d5 d6 where we subtract the number on the left from its neighbor on the right to obtain the next row. And proceed to obtain the equation: 1/2(d6)x2 + (d4(1/2d6))x +d1 = 1/2(e6)y2 + (e4(1/2e6))y + e1 This is a Diophantine equation of the form A x2 + Bxy + C y2 + Dx + Ey + F = 0. While there are analytical methods to solve this type of equation they involve the use of factorization which we wish to avoid. Hence we will go by the rational point on conics route. Using A x2 + Bxy + C y2 + Dx + Ey + F = 0 and the equation of the line given by y = y1 +m(xx1) and considering the sum of roots we obtain the parametrization of x given by x = [( x1 Cm2 (2C y1+ E)m – (By1 + Ax +D)] / ( Cm2 + Bm + A) (2) and x1 and y1 are the solutions to the equation at k1 In our case the above Diophantine equation is actually of the form x2 + Dx + F1 = y2 + Ey + F2 = k ( where F = F1 –F2) and the k is the same k as in (1) So we just consider x2 + Dx + F1 = k (3) and substitute (2) into (3) to get the parametrized version of (3) Now for a number N with only two prime factors there will only be two integer values of k satisfying (3) one of which k1 can be found. Hence all rational solutions to (3) have to be multiples of either k1 or k2. To find the other value we run through various values of m clear fractions and see if they are 0 (mod k1). If they are we discard these values. If they are not they have to be 0 (mod k2 ) we store them until we get 2 such values and compute their GCD to obtain k2. Having obtained k2 we can work out the two prime factors of N. 
20061106, 01:37  #2  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
The typesetting in the posting is a little messed up, but ok in the pdf. I suppose b_{[I]n[/I]} is the smallest integer so that b_{[I]n[/I]}^{2} ≥ k_{2[I]n[/I]1}. Also, I think you're using the variable name k for different things. If so, can you clarify?
I can't say I understand how the finite differences or finding the rational on the conic work, but someone with more experience very well might. Just one question: Quote:
Alex Last fiddled with by akruppa on 20061106 at 02:03 

20061106, 01:58  #3 
Nov 2006
Singapore
3×5^{2} Posts 
Firstly apologies for the typesetting. I just cut and paste from my original document and didn't realise that it will end up all funny.
For your second question, I'll provide a numerical example. we start with 901: sqrt(901)<31^2 so 31^2 901 = 60 sqrt(60)<8^2 so 8^260 = 4 and 4 = 2^2 so 2^2  4 = 0 so (31^2 + 2^2)  (8^2) = 901 then (31^2 + 2^2 + k)  (8^2 + k ) = 901. where the k values will make the expressions in the brackets a perfect square.(I am trying to do something similar to Fermat's factoring algorithm.For a semiprime there will only be two such values. The k's with a subscript are different from the k's in the bracket but we do not need the k's with the subscript subsequently. I think I will change my original to make things clearer. 
20061106, 02:05  #4 
Nov 2006
Singapore
75_{10} Posts 
Also the running through m is the part I've been unable to do, since I am unable to program. But my reasoning is that we have a hyperbola which has. infinitely many rational points. These points are a multiple of k1 or k2 only.(Otherwise our semiprime will have more than 3 factors!) Hence we have a 50/50 chance in infinity of hitting a multiple of either k1 or k2. What I'm hoping is that is if there is a consensus that the math is sound that someone might be able to help me code and test the algorithm. If there are any flaws in the math it will be spotted here and no one will have to waste too much time.
Visu 
20061106, 11:59  #5 
Nov 2006
Singapore
75_{10} Posts 
Made some alterations to the original pdf to avoid using the same symbols for different variables. This should sort out some of the confusion
Cheers Visu 
20061106, 19:44  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
You are simply trying to factor 901 via Fermat's Method of expressing it as the difference of two square. We have 35^2  18^2 = 901. You simply choose to represent 35^2 = 1225 as (31^2 + 2^2 + 260) and 18^2 = 324 as (8^2 + 260) This is a very roundabout and unnecessarily expensive way of finding a representation as the difference of two squares. > It is *useless* (sorry to burst your bubble) Fermat's method itself is pretty much useless for any composites over 25 digits. 

20061106, 20:00  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
As far as I understand it, his idea was to contruct a good k more efficiently by looking for rational points on a conic. I don't understand the idea well enough to say anything about its merit. Is the approach inefficient?
Alex 
20061106, 20:51  #8 
Aug 2003
Snicker, AL
7×137 Posts 
I looked at this thread yesterday and recognized it as a variant of Fermat's squares method. The method is inefficient because the underlying calculations involve finding square roots and performing division. Computers don't do these very efficiently so add the inherent inefficiency of the method plus the inefficiency of coding this into an algorithm and the performance is unacceptable by comparison with other methods.
I put together a crude routine in ubasic and found out just how bad it really was. Interestingly enough, there are two ways of applying Fermat's squares method, one of which I was unable to find documented. This thread's approach appears to be based on Fermat's original method. The second method is based on finding the largest square greater than the number to be factored. Neither is of much real use except as trivia answers. Fusion Last fiddled with by Fusion_power on 20061106 at 20:53 
20061106, 23:10  #9  
Nov 2006
Singapore
1001011_{2} Posts 
Quote:


20061106, 23:15  #10  
Nov 2006
Singapore
3·5^{2} Posts 
Quote:
Well how bad is it really? Like I said I could use the feedback. Any data that you generated would also be appreciated. Visu 

20061106, 23:27  #11 
Nov 2006
Singapore
1001011_{2} Posts 
Correct me if I'm wrong but division and square rooting are still performed in polynomial time. The first step contains no division and maybe at most 8 instances of square rooting and even then the last few numbers become so small that the calculation can be performed on a pocket calculator.
No division or finding of square roots is involved in the second step of finding the conic representation of the numbers. Until the final step of finding k we do not need to do any division and even in that step we are essentially performing a test of divisibility (by taking mod of k1) which to me seems to be a common feature of all primality testing or factorizing methods. Visu 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Alternativelygifted factoring algorithm  Prime95  Miscellaneous Math  72  20151026 00:14 
Shor's Factoring Algorithm  does it even work?  Citrix  Factoring  37  20080816 14:19 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
division/remainder algorithm (trial factoring)  TheJudger  Math  4  20071018 19:01 