I like to give an another method for factorization. Below method is not an efficient method , but it is a method to factorize. I dont know it already exist or not , which mean I have searched for this process on internet , But I did not find this method. So , may be I missed the page where this method already is , or it did not exists. P-n method: This method goes around the fact that , Any number P can be written as p - n + n ; n is any number . Here p is an odd number and is not a prime number. If p0 is the given number. then if p0 = p1 * p2 ; here p1 < p2 p0 - n = x1 * x2; here x1 < x2 then p0 = (p0 - n ) + n ==> p0 = ( x1 * x2 ) + ( |p1 - x1| * x2 ) - ( ( |p1 - x1| * x2 ) - n ) ; or p0 = ( x1 * x2 ) - ( |p1 - x1| * x2 ) + ( ( |p1 - x1| * x2 ) + n ) ; assuming |p1-x1| is the least difference . Total no.of.loops = 2 * 2 * |p1 - x1| * divisor arrangements divisor arrangements is explained below. p-1 method. (later explained p-n method) ------------- for example consider p-1 method explained with an example . If given p is odd then p-1 is always an even number . Let P0 = 919829 = 587 * 1567, then p-1 = 919828 = 2 * 2 * 229957 So , here we have to arrange the p-1 as the product of two divisors . like divisors_arrangement = 2*459914 or 4*229957 *** This divisor arrangement is important because we dont know, for which arrangement we will get an answer. Here I am taking p-1 = 4*229957 As we know that p = (p-1) + 1 ; so p = (4*229957) + 1 ==> p = (4*229957) + (583 * 229927) - ( (583 * 229927) -1) ==> p = (4 * 229957) + (583 *229927) - 134064930 ==> p = (229957 * 587 ) - 134064930 Here this 134064930 is exactly divisible by 587 as 134064930 = 587 * 228390 so p = (229957 * 587 ) - ( 587 * 228390) ==> p = (587 * (229957 - 228390)) ==> p = (587 * 1567) ------- which is the required solution. Here it is inefficient because it requires 587 - 4 no .of loops to factorize . i.e . if a number n = n1 * n2 ,if n1 < n2 , and n-1 = (2^a0) * n3 , then it requires ( n1 - (2^a0) ) = lowest factor of p - lowest factor of (p-1) loops to factorize. It is not necessarily to be difference of lowest factors. It may be "largest factor of p - largest factor of (p-1)) , if the difference is negative modulus of the number is the required loops , the least of the difference is the minimum no.of loops we are going to run . also since there may be |negative difference|< +ve difference , we are going to check total loops = (2 * the least difference ) * no.of.arrangements of divisors Another cause for inefficiency is the no.of.arrangement of p-1 factors as the product of two divisors. if there a "h" ways for the arrangement then the total no.of loops to factorize is = [ h * ( n1 - (2^a0) ) ] The no.of.loops can be further decrease by , factorizing 229957. It can be done by taking p1 = 229957 and calculate p1 -1 and then proceeding the same steps as done above. this must be continued until we get pn-1 = (2^an)*prime number , at some point of n. Here 229957 can be factorized into = 7*7*13*19*19 for the above number 919829 the total number of loops decreased from 583 to 433 loops . p-n method: --------------- based on p0 = (p0 - n ) + n The problem in above method is we have to do approximately the factor<sqrt(p) loops to factorize . since the above number can be factorized even further we have decreased the no.of .loops . But If numbers like 33250423 = 4363 * 7621= p0 has p0-1 = 6 * 5541737 . where 5541737 is a prime number then the total no.of .loops to be run = 4363 - 6 = 4358 loops . So replace (no.of.digits of p0 )/2 of p from left as zeros . i.e do p0 - 423 = 33250000 , now factorize this number using the same method for which you will get one of its divisors as 4375 , which means 33250000 = 4375 * 7600 ; so the loops to be run = 2* |4363 - 4375 | * no.of.divisors arrangements = (12 * no.of.divisors arrangements ) loops. Here also there exits an inefficiency , 1. as the no.of.factors of p0 - n increases the no.of .ways of divisors arrangement increases. There by increasing the no.of.loops. 2. It is sure that by replacing (no.of.digits of p0 )/2 zeros will get one of the divisor of p0-n nearest to the divisor of p0 . But I am not sure about the exact no.of zeros that has to be replaced . because, ---the number 694,891,321,868,591 = 15487811 * 44866981 will have the nearest divisor when no.of.zeros to be replaced is, ( (no.of.digits of p0 )/2 - 1 ) , i.e for 694,891,321,000,000 having divisor 15446320 . giving a difference of 41491 ; ---and for number 49976497 = 6343 * 7879 ; we will get minimum when zeros = ( (no.of.digits of p0 )/2 - 1 ) i.e ., at 49976000 have divisor 6247 , giving a difference of 91;
Perhaps I'm not following well enough but I can't help but feel that seems a little too engineered, like you know what you're looking for. You do the well known analysis trick of adding zero in the form of +(X-X) but in order to pick X, which you also have a factorisation for, it seems a little wishy-washy. I can see how its useful once you know it but your method of constructing it isn't clear. And worse than that, you admit that not all paths you go down might lead to the answer, some of them can't have this method applied, which is pretty much a critical flaw in any algorithm unless you can show that your method is so fast that it can be run multiple times, to find the answer eventually, and still out pace other methods. I don't know how familiar you are with computational complexity but the speed of an algorithm is typically measured in the amount of algorithmic steps it takes to work on a given size input. For instance, if you have 2 vectors of length N then to computational complexity of adding them is O(N), ie if you double the length of the vectors you double the number of steps needed to add them. If you want to act an NxN matrix on an N component vector then you have to do O(N^2) steps, ie each row in the matrix, of which there are N, is dotted with the vector, so you need to do N multiplications and then N-1 additions, ie each output entry needs 2N-1 steps so overall you need N(2N-1) ~ O(N^2) steps. Double the value of N and you basically quadruple the work. If you have a look on Wiki for various factorisation methods you'll see that people put in a lot of effort in shaving off bits of the complexity, because if you're trying to factorise a 10,000 digit integer a minor decrease in complexity can be a huge saving. Fourier transforms are used and they have complexity O(N log N), which is much faster than some naive approaches to factorisation which can be O(N^2) or O(N^3). For instance, searching for primes can be done by using the simplest number sieve, chucking out all multiples of a given number. This is algorithmically simple to code and understand but its terribly slow (though the best known method is a generalised number sieve). Like with so much in life, the simplest road is rarely the best. Another plus for such methods is that they are certain to work (well, except certain quantum ones), they generally don't have the "I have to guess which one to try and then start again if I'm wrong" issue your method has. Again, this is typically at the expense of simplicity in terms of understanding but well worth it when it saves you thousands of CPU hours.
Where did 583 come from in the second step? Also.. Is what AN wrote true? Or did you mean that this method would work for all odd p, but only a single combination of the factors of (p-1) which can be difficult to find if (p-1) has many factors?
