View Single Post
 2017-02-26, 20:16 #1 ThiloHarich     Nov 2005 101 Posts A simple idea for factoring numbers While palying with the fremat equation i had an idea which might be used for finding integer factors of a product. The idea is to write the fermat equation in a different way. Instead of having a sum of two squares and the number n in an equation we have an equation which exists out of four products. The size of the numbers in the equations is reduced. Unfortunately I was not able to come up with an algorithm that works for general numbers with a guaranteed speedup. Maybe you can help develop such an algorithm or by preventing myself from putting much effort in a stupid idea. It is based on a different representation of the fermat equation q*p = n = x^2 - y^2 We want to solve an equation of the form: n = p*q = (x+y) * (x-y)= x^2 - y^2 (1) It can also be written as x^2 - n = y^2 (2) This gives a factorization of n. If we already have a relation of the form x^2 - n = y^2 + e (3) we try to get a new equation out of this without the error e, such that we get an equation like we have it in (2). Out of equation (3) we construct the following equation: (x+ae)^2 - n = y'^2 + e' (4) here we hope to get e' = 0 in order to we have a solution for (2). a is an integer or at least a*e is an integer. Why should this work? If we take equation (4) with e’=0 and subtract equation (3) from it we get: (x+ae)^2 - n = y'^2 (5) - (x^2 - n = y^2 + e ) ---------------------------------- (x+ae)^2 - n - x^2 + n= y'^2 - y^2 - e x^2+2xae + (ae)^2 - n - x^2 + n = y'^2 - y^2 - e 2xae + (ae)^2 + e = y'^2 - y^2 e*(2ax + a^2e +1) = y'^2 - y^2 e*(2ax + a^2e +1) = k(2y+k) (6) Basically two things have happened here - The probability to fulfil this new equation is higher as a fulfilling the original equation - From one equation for one x we can jump to an other solution which is far away Concerning 1) Both equations refer to the same solution, but equation 6 has a better chance to be fulfilled since: If q and p are primes, there is only one solution y’. But there might be many splits of y’ in y+k and k such that k and y fulfill some conditions In equation 5 the numbers on the right are very specific, since they are squares. In equation 6 they are products. The size of the numbers on both sides are reduced Both sides have (nearly) the same structure So we can extend the regular factorisation method from fermat by an additional step. When checking if x^2 - n is a square we also check if (x+e)^2 - n is a square, where e = x^2 - n - ceil(x^2 - n)^2. Examples: n=32003*16001 x=22632 = ceil(Sqrt(n)) + 2 // only two steps in the regular fermat method x^2 - n = 356^2 - 685 y = floor(sqrt(x^2-n)) = 356 e = -685 = 137 * 5 we choose a=2 e * (2ax + a^2e - 1) = 137*5 * (2*2* 22632 + 4* 685 +1) = 137*5 * 93269 = 137*5 *11 * 61 * 139 choose k= 5*11*139 = 7645 k+2y = 7645 + 2*356 = 8357 = 137*61 i.e. x+a*e = 22632 + 2*685 = 24002 and y’=y+k = 356 + 7645 = 8001 is a solution. instead of searching a*e = 2*685 = 1370 steps with the regular fermat method, we only need 2 steps to get to the solution. Example a=1 n=10037 * 4339 Y’ = 7188 x= 6627 , s=27 e=-561 =- 3* 11* 17 2x + e + 1 = 2*6627 + 1 + 561 =(2x+1) + e = 5*11*241 - 3* 11* 17 = 2^3* 11 * 157 y=605 k= 2849 - 605 = 2244 = 2*2*3*11*17 2y+k = 2*11*157 a=4 n=10037 * 4339 Y’ = 7188 x= 6600 e=147 = 3* 7 * 7 a(2x + a*e) - 1 = 4(2x + 4*e) - 1 = = 8*6600 + 16*147 - 1 = 52800 + 2351 = 131* 421 y=605 k= 2849 - 98= 2751=3* 7*131 2y+k = 98*2+ 2751= 7* 421 A simple (java) algorithm using the facts from above with a=1 is this: public long findFactor(long n) { double sqrt = Math.sqrt(n); long x = (int) Math.ceil(sqrt); while (true) { long right = x * x - n; long y = (int) Math.ceil(Math.sqrt(right)); long error = y * y - right; long x2 = x + error; long y2 = x2 * x2 - n; double sqrtY2=Math.sqrt(y2); if (sqrtY2 == (long) sqrtY2) { return (long) (sqrtY2 + x2); } x+=1; } } The algorithms always finds a solution (for odd factors). Even when the facts above does not apply. Then the error is 0, and the solution is found by the original fermat method. In this case we have to apply the expensive calculation of the square root twice. This means the algorithm takes twice the time compared to the original Fermat method. There are some more slight improvements, but I could not find an algorithm which provides a speedup for each number compared to the original fermat method.