mm-2299 Surrogate factoring is what I call methods that try to factor a target M by using the factorization of another number I call the surrogate, which I usually label T. I've been looking for a perfect surrogate factoring algorithm that will always factor a target M. The two main quadratics in this approach are yx^2 + Ax - M^2 = 0 and yz^2 + Az - j^2 = 0 where M is the target to be factored, j is some non-zero natural coprime to M that is usually chosen to be less than M, and T = M^2 - j^2. Then y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2 and you can substitute out y to get x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) where the square roots relate Ax to the factorization of T and j, and Az is related to the factorization of T and M. I wish to focus on Az because there must exist some integer Az that has a single prime factor of M, which follows from x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so let r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so that x = zr where r is a prime factor of M, then using my starting quadratics, and substituting out x, I have yr^2 z^2 + Arz - M^2 = 0 with yz^2 + Az - j^2 = 0 so multiplying the second by r^2, I have yr^2 z^2 + Arz - M^2 = 0 with yr^2 z^2 + r^2 Az - r^2 j^2 = 0 and subtracting the first from the second gives (r^2 - r)Az = r^2 j^2 - M^2 and dividing gives Az = (j^2(r + 1) - T/(r-1))/r so I now have a result that relates the prime factors of M to the factorization of T. Also though looking again at (r^2 - r)Az = r^2 j^2 - M^2 which is (r - 1)Az = rj^2 - M^2/r I have that if r-1 shares prime factors with j, then Az cannot be an integer, as j is coprime to M. There are two ways to handle that situation where the simplest is to have j have few prime factors, especially small ones like 2, 3 and 5. The other is to assume if you don't get a factorization that some prime factor p f j is blocking and consider pT/(r-1) looking for that to be an integer. That complete the theory for surrogate factoring which is then a solution to the factoring problem. James Harris Surrogate factoring is what I call methods that try to factor a target M by using the factorization of another number I call the surrogate, which I usually label T. I've been looking for a perfect surrogate factoring algorithm that will always factor a target M. The two main quadratics in this approach are yx^2 + Ax - M^2 = 0 and yz^2 + Az - j^2 = 0 where M is the target to be factored, j is some non-zero natural coprime to M that is usually chosen to be less than M, and T = M^2 - j^2. Then y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2 and you can substitute out y to get x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) where the square roots relate Ax to the factorization of T and j, and Az is related to the factorization of T and M. I wish to focus on Az because there must exist some integer Az that has a single prime factor of M, which follows from x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so let r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so that x = zr where r is a prime factor of M, then using my starting quadratics, and substituting out x, I have yr^2 z^2 + Arz - M^2 = 0 with yz^2 + Az - j^2 = 0 so multiplying the second by r^2, I have yr^2 z^2 + Arz - M^2 = 0 with yr^2 z^2 + r^2 Az - r^2 j^2 = 0 and subtracting the first from the second gives (r^2 - r)Az = r^2 j^2 - M^2 assume that r = n/d, where n and d are coprime integers, then (n^2 - nd)Az/d^2 = (n^2 j^2 - d^2 M^2)/d^2 which is (n^2 - nd)Az = (n^2 j^2 - d^2 M^2) and use j^2 = M^2 - T, to get (n^2 - nd)Az = (-n^2 T + n^2 M^2 - d^2 M^2), so n(n-d)Az = (-n^2 T + (n-d)(n+d) M^2) so Az = (-n T/(n-d) + M^2 (n+d)/n) proving that n-d must be a factor of T. Now since x = zr, then x = zn/d, so Ax = Azn/d. r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) I know that d must share prime factors with 2j^2 - 2Az, so it must be coprime to Az except possibily factors shared with 2 or j^2. Now I can use z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) to get x = z(2M^2 - 2Ax)/(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2)) and I want to focus on the denominator as that must have d as a factor. Well, let's look at *rational* g_1 and g_2 such that g_1 g_2 = Tj^2 and consider the positive solution of the square root so then Ax = g_1 - g_2 + 2j^2, so substituting into (-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2)) and taking the positive of the square root, I have (-g_1 + g_2 - 2j^2 + g_1 + g_2) which gives 2g_2 - 2j^2 and now let g_2 = f_1 d_2/d_1, where f_1 is an integer factor of Tj^2, with f_2 being the other factor and d_1 is a factor of d with d_2 being the other factor where d_1 is coprime to d_2, so then g_1 = f_1(d_2)/d_1 and g_2 = f_2(d_1)/d_2 so that g_1 g_2 = f_1 f_2 = Tj^2 as required. Then substituting gives Ax = f_1 (d_2)/d_1 - f_2(d_1) /d_2 + 2j^2 = (f_1 d_2^2 - f_2 d_1^2 - 2j^2 d_1 d_2)/d_1 d_2. showing that that d_1 d_2 does equal d. Now substituting into 2g_2 - 2j^2 I have 2f_1 d_2/d_1 - 2j^2, which is 2(f_1 d_2 - 2j^2 d_1)/d_1 and that d_1 in the denominator will multiply up so that I have x = z(d_1 d_2M^2 - (f_1 d_2^2 - f_2 d_1^2 - 2j^2 d_1 d_2))/d_2(f_1 d_2 - 2j^2 d_1) and since d_2 is coprime to d_1 that requires that d_1 be a factor of f_1 for the denominator to have d as a factor. But f_1 is a factor of Tj^2, so d_1 and therefore d_2 is a factor of Tj^2. Going back to Az = (-n T/(n-d) + M^2 (n+d)/n) and concentrating on T/(n-d), I can use d_1 d_2 = Tj^2, to have T/(n - d_1) and multiplying top and bottom by d_2, I have Td_2/(d_2 n - Tj^2) and now multiplying the top by d_1, I have that T^2 j^2/(d_2 n - Tj^2) must include cases where n is given as you consider integers f_1 and f_2, such that f_1 f_2 = T^2 j^2, and take the gcd of f_1 + Tj^2 with M, to get a prime factor. James Harris Here we go again...should be it though... Surrogate factoring is what I call methods that try to factor a target M by using the factorization of another number I call the surrogate, which I usually label T. I've been looking for a perfect surrogate factoring algorithm that will always factor a target M. The two main quadratics in this approach are yx^2 + Ax - M^2 = 0 and yz^2 + Az - j^2 = 0 where M is the target to be factored, j is some non-zero natural coprime to M that is usually chosen to be less than M, and T = M^2 - j^2. Then y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2 and you can substitute out y to get x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) where the square roots relate Ax to the factorization of T and j, and Az is related to the factorization of T and M. I wish to focus on Az because there must exist some integer Az that has a single prime factor of M, which follows from x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so let r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so that x = zr where r is a prime factor of M, then using my starting quadratics, and substituting out x, I have yr^2 z^2 + Arz - M^2 = 0 with yz^2 + Az - j^2 = 0 so multiplying the second by r^2, I have yr^2 z^2 + Arz - M^2 = 0 with yr^2 z^2 + r^2 Az - r^2 j^2 = 0 and subtracting the first from the second gives (r^2 - r)Az = r^2 j^2 - M^2 assume that r = n/d, where n and d are coprime integers, then (n^2 - nd)Az/d^2 = (n^2 j^2 - d^2 M^2)/d^2 which is (n^2 - nd)Az = (n^2 j^2 - d^2 M^2) and use j^2 = M^2 - T, to get (n^2 - nd)Az = (-n^2 T + n^2 M^2 - d^2 M^2), so n(n-d)Az = (-n^2 T + (n-d)(n+d) M^2) so Az = (-n T/(n-d) + M^2/n) proving that n-d must be a factor of T. Now since x = zr, then x = zn/d. r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) I know that d must share prime factors with 2j^2 - 2Az, so it must be coprime to Az except possibily factors shared with 2 or j^2. Now I can use z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) as the x must have 1/r as a factor, so x = z(2M^2 - 2Ax)/(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2)) and I want to focus on the denominator as that has d as a factor. Well, let's look at *rational* g_1 and g_2 such that g_1 g_2 = Tj^2 and consider the positive solution of the square root so then Ax = g_1 - g_2 + 2j^2, so (-g_1 + g_2 - 2j^2 + g_1 + g_2) and (2g_2 - 2j^2), and now let g_2 = f_1 d_2/d_1, so 2(f_1 - j^2 d_1) where f_1 is an integer factor of Tj^2, with f_2 being the other factor and d_1 is a factor of d with d_2 being the other factor, where g_1 = f_1(d_2)/d_1 and g_2 = f_2(d_1)/d_2 so Ax = f_1 (d_2)/d_1 - f_2(d_1) /d_2 + 2j^2 = (f_1 d_2^2 - f_2 d_1^2 - 2j^2 d_1 d_2)/d_1 d_2. Now focusing again on 2(f_1 - j^2 d_1) since f_1 f_2 = Tj^2 it's possible that f_1 shares prime factors with j^2. Letting h_1 be shared factors, and *assume* f_1 is coprime to d_1, I have f_1/h_1 - j^2 d_1/h_1 = d now looking at the negative solution above where indices shift, and there is a sign change, I have -f_2/h_2 - j^2 d_2/h_2 = d and letting c_1 = f_1/h_1, and c_2 = f_2/h_2 and letting m_1 = j^2/h_1 and m_2 = j^2/h_2 I have c_1 - m_1 d_1 = -c_2 - m_2 d_2 and now using d_2 = d/d_1, I have c_1 d_1 - m_1 d_1^2 = -c_2 d_1 - m_2 d, so m_1 d_1^2 - (c_1 + c_2)d_1 - m_2 d = 0 and solving for d_1 d_1 = (c_1 + c_2 +/- sqrt((c_1 + c_2)^2 + 4dj^2))/2g_2 where I have a sign problem, but meaning that either d, c_1 or c_2 is negative, but more importantly, c_1 c_2 = T, with the assumption that d_1 and d_2 are coprime to T. But that would force d = T, but with n a prime factor of M, n-d is coprime to T so d cannot equal T. Therefore the assumption of coprimeness between f_1 and d_1, also made between f_2 and d_2 but not specifically stated, is false, proving that d must share prime factors with T. Further since c_1 c_2 only have prime factors of Tj^2, it must be true that d is a factor of T. Ok, so where's a possible hole? Well I'm looking at sqrt((c_1 + c_2)^2 + 4dj^2) and saying that because c_1 and c_2 are factors of Tj^2 that d must be as well, as that's what fits. I think I'm right, but I want to think some more on that point. James Harris I think I'm right, but I want to think some more on that point. James Harris Is that why I smelled wood burning :-) Adding to what I thought yesterday was a complete theory, as I may have just stopped a little too soon with the derivation... Surrogate factoring is what I call methods that try to factor a target M by using the factorization of another number I call the surrogate, which I usually label T. I've been looking for a perfect surrogate factoring algorithm that will always factor a target M. The two main quadratics in this approach are yx^2 + Ax - M^2 = 0 and yz^2 + Az - j^2 = 0 where M is the target to be factored, j is some non-zero natural coprime to M that is usually chosen to be less than M, and T = M^2 - j^2. Then y = (M^2 - Ax)/x^2 = (j^2 - Az)/z^2 and you can substitute out y to get x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax) where the square roots relate Ax to the factorization of T and j, and Az is related to the factorization of T and M. I wish to focus on Az because there must exist some integer Az that has a single prime factor of M, which follows from x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so let r = (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) so that x = zr where r is a prime factor of M, then using my starting quadratics, and substituting out x, I have yr^2 z^2 + Arz - M^2 = 0 with yz^2 + Az - j^2 = 0 so multiplying the second by r^2, I have yr^2 z^2 + Arz - M^2 = 0 with yr^2 z^2 + r^2 Az - r^2 j^2 = 0 and subtracting the first from the second gives (r^2 - r)Az = r^2 j^2 - M^2 assume that r = n/d, where n and d are coprime integers, then (n^2 - nd)Az/d^2 = (n^2 j^2 - d^2 M^2)/d^2 which is (n^2 - nd)Az = (n^2 j^2 - d^2 M^2) and use j^2 = M^2 - T, to get (n^2 - nd)Az = (-n^2 T + n^2 M^2 - d^2 M^2), so n(n-d)Az = (-n^2 T + (n-d)(n+d) M^2) so Az = (-n T/(n-d) + M^2/n) proving that n-d must be a factor of T. so I now have a result that relates the prime factors of M to the factorization of T. Well that's what I have so far. I don't see anything related to the blocking prime issue I raised before and integer Az must exist. The problem now is, how do you get d? James Harris [JSH] [...] [...] [...] If r is a prime, and r = n/d where gcd(n, d)=1, then the only solutions are n=+/-r and d=+/-1. solutions are Hmmm...where did you get that? If that's correct then all you need to do is loop through f_1 + 1 and f_1 - 1, but I take it that didn't work, right? The correct algorithm that I can now derive theoretically as I've moved from the assumption of integer r, and figured out how to do it is as follows: With T/(n-d) d must be a factor of T, so you you loop through integers f_1 and f_2 such that f_1 f_2 = T, and with a given f_1 you then loop through the factors of f_2 to get d, as d is then a factor of f_2, and then calculate f_1 + d and take the gcd with M, for each possible integer d. I'm going to go ahead and post the derivation in a bit, but that's the algorithm. I already basically did so but what I gave was a little messy so I'll clean it up and explain in more detail. And it should work for any natural j coprime to M, as even or odds or blocking primes don't matter. James Harris [JSH] [Tim Peters] [JSH] prime, it's just that r is an integer that matters). Then gcd(n, d)=1 implies gcd(rd, d)=1, but d certainly divides gcd(rd, d) (d divides both inputs, so d is _a_ common divisor, so d divides the _greatest_ common divisor too), so d divides 1, so d is +/-1. Then n=rd must be +/-r. More simply, that gcd(n, d)=1 means that n/d is a rational in normalized form, and the normalized form of any integer expressed as a rational has unit denominator. The last algorithm I tested yesterday was: # Generalizing away from j=1, if the algorithm is: # # 1. Pick an integer j in 1..M-1. # # 2. T = M^2 - j^2. # # 3. For each integer f (positive or negative) dividing Tj^2, # compute g = gcd(f+1, M). Report that g is a factor if # 1 < g < M. and (a) that certainly didn't work; but, (b) it didn't check f-1 directly. However, for any f with f|Tj^2, -f divides Tj^2 too, so gcd(-f+1, M) was checked. And gcd(-f+1, M) = gcd(1-f, M) = gcd(-(1-f), M) = gcd(f-1, M), so f-1 was checked indirectly when (-f)+1 = 1-f was considered. As shown in another post, the smallest counterexample for that variation is M=15 at j=14. Oh, you're still trying r an integer, but r can't always be an integer. That's been the point of all this effort today. is a d)=1 both common normalized has and directly. was M), so I stepped through a direct calculation of r when you pointed out an example where the theory I'd given didn't work, and it was in fact a fraction. I realized that I'd just made a false assumption that r was an integer and began working out a fuller theory where it's a fraction. It only took a little bit of effort to find out that instead of T/(r-1) you have T/(n-d), where n is an integer prime factor of M, and d is to be determined, while I've been pushing for d to be a factor of T. moved as f_2 the the or variation is Hmmm...yeah, you're right, as what I have doesn't work there. What does work is d=4, and I've been tossing off factors of 2, left and right in my derivations thinking that they don't matter. Still, it's not enough to just toss in some, so I'll go see if I can't figure out what's wrong from my latest work. It still might be that even j is the problem, yet again, despite my efforts to allow even j. We'll see... James Harris Oops! -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com If n and d are coprime, then n/d is already in canonical form. If r is an integer (any integer, not just a prime), then d must be unitary. This should be obvious to any child who studied fractions and pondered the problem for a little while. Alas, it is too much to be expected of James Harris. D.8ecio Answer must be here with x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/ as I have (-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) = (2M^2 - 2Ax)/(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2)) so I need to concentrate on (-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2)) as it must share prime factors with d, or better yet its numerator must as Ax may be a fraction. Well, I know it's a fraction a lot of the time as the algorithms that have checked it as an integer haven't always worked. Well, let's look at *rational* f_1 and f_2 such that f_1 f_2 = Tj^2 and consider the positive solution so that Ax = f_1 - f_2 + 2j^2, so (-f_1 + f_2 - 2j^2 + f_1 + f_2) is what I have, so (2f_2 - 2j^2), and now let f_2 = a/d_1, so 2(a - j^2 d_1) where d_1 is a factor of d, and that must share prime factors with d, but I have from before Az = (-n T/(n-d) + M^2/n) and 'a' is likely to share some prime factors with j^2, since f_1 f_2 = Tj^2 but not all, so let a = g_1c, where g_1 is that shared factor, and j^2 = g_1 g_2, so 2g_1(c - g_2 d_1) and assuming that I have coprimeness between c and g_2 d_1, I have c - g_2 d_1 = n-d and I can subtract above to get a second solution with the same value, so with c_1 c_2 = Tj^2, and g_1 g_2 = j^2, I have c_1 - g_2 d_1 = -c_2 - g_1 d_2 (hope I didn't mess up signs) and now using d_2 = d/d_1, I have c_1 d_1 - g_2 d_1^2 = -c_2 d_1 - g_1 d, so g_2 d_1^2 + (c_1 - c_2)d_1 - g_1 d = 0 and solving for d_1 d_1 = (c_2 - c_1 +/- sqrt((c_1 - c_2)^2 + 4dj^2))/2g_2 well, assuming I didn't mess something up, as I did kind of cruise through, it looks to me like d is where T usually is! Well that was slap-dash but if it's correct, then d does in fact merely have prime factors of T, or it is T...no, it can't be T itself as that wouldn't work, so it looks like it's a factor of T. So you need T/(n-d) where d is a factor of T, which is no fun as it looks like it means that you find some factor of T, and then check through the *other* factors of T for your d, as it can't be that same factor. I need to go back through carefully... James Harris [JSH] [...] Whenever you post a new algorithm A(M, j), the first thihg I do is feed it to this (Python) function: def try_small(A, limit=10000): # Try all odd composite M, not the square of a prime, < limit; # and at all j in 1..M-1. for M in xrange(3, limit, 2): if M % 1000 == 1: print up to, M fs = fac(M) if len(fs) == 1 or (len(fs) == 2 and fs[0] == fs[1]): continue # prime or square of a prime for j in xrange(1, M): g = A(M, j, early_out=True) if not 1 < g < M: print %5d %5d % (M, j) fac(M) returns a list of the prime factors of M, using dead simple trial division. That's very efficient for numbers this small. You could easily write such a program in Java too, right? Then you could find small counterexamples yourself. No algorithm yet has gotten to M=10000 without many of 'em; none have gotten to 1000 yet without finding at least one. For example, let's try this new one: Running try_small() on an implementation of that finds many counterexamples quickly, staring with M=15 at j=14: 15 14 21 20 27 26 35 12 35 18 35 32 35 34 45 44 ... You could then analyze them to determine what went wrong. M = 15 j = 14 T = 15**2 - 14**2 = 29 and is prime Therefore the only ways to split T are f_1 f_2 --- --- 1 29 -1 -29 29 1 -29 -1 and it's easy to check that gcd(k, M) isn't 3 or 5 for any k of the form +-29 +-1 The closest it gets is gcd(30, 15) = 15. own code to look for small counterexamples. To get away from the crank label, you don't need to post a new method every day; quite the contrary, you need to refrain from posting new methods at least until you find one for which 4-digit (or even smaller) counterexamples don't exist -- and you especially need to refrain from claiming you've solved the problem when small counterexamples are so easy to find by anyone who bothers to look for them. Not that it matters much, but can one pass functions as parameters to functions in Java? One could say the same thing for most of his work. If he did that then he'd have nothing to do, and more important no way to affirm daily that he's found yet another solution to a problem that has mystified the rest of us. ************************ David C. Ullrich [Tim Peters] [David C. Ullrich] I haven't mucked with Java for years now, but it was true that you could not last time I played with it. That's OK, there are many ways to get the same The object then has easy ways to record and reveal all sorts of info about the factoring attempt. Each new algorithm is implemented by a new class, but implementing the same JSH-like factoring method interface, so that nothing in try_small() (or other test drivers) needs to change. Writing multiple classes implementing a common interface is a common approach in Java too. Explaining all that would have been a distraction here, though. ... Really? Checking claims about factoring is so darned easy, because a counterexample amounts to no more than doing integer arithmetic, and that's easy to program and to verify. Checking, e.g., whether a particular spelling of a prime-counting algorithm is or is not equivalent to some other spelling is much more open to debate; ditto whether a particular ring is well-defined (or even exists), and so on. Those don't reduce to showing that 2+2 =/= 5, or at least not without agreement on the precise meanings of the terms involved; I think we make a semblance of progress here just because everyone agrees 2+2 =/= 5 when it's pointed out that 2+2 equals 4. Oh, speak for yourself. I factored the RSA challenge numbers the day they Yes James, when you claimed that your theory was complete, and that the math world would be turned on its ear, and all the news channels would be covering your breakthrough, you were very stupid, but that is not surprising, very par for the course for you. But keep up your research, at least it keeps you off the streets. The longer you stay huddled up in the dark on your computer spewing out nonsense, the better it is for the people near you in the real world. Is this now what you call a complete theory as advertised in the title of this thread? -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com Well, of course the theory wasn't complete. That's a stupid question. Now then, if my latest is correct, then the proper algorithm comes from T/(n-d) where you loop through integers f_1 and f_2 such that f_1 f_2 = T, and taking f_1 you then loop through the factors of f_2, that is let g_1 g_2 = f_2, then you take f_1 + g_1 and take the gcd with M, for each possible integer g_1. So there's a double loop. Well there goes the time savings from using T, versus T^2, but I think it's still better than T^6. If that's correct, then...sigh, let's wait and see if it's correct. I need to double-check the calculations that indicated d is just a factor of T. James Harris Erme -then why did you title the thread 'complete theory - who's being stupid? Min -- Your ignorance is dangerous. Your confidence based on your ignorance is dangerous. Yet another stupid question, as I *thought* it was complete. Duh. Now I'm ready to test the current algorithm. It codes easier, but I'm hesitating as what if it doesn't work? The algorithm for those who wish to test is given a target M that you wish to factor, pick a natural j less than M that is coprime to it, and then calculate T, using T = M^2 - j^2 oh, if you're really wondering about how to pick j, just pick an *odd* j, as someone already posted a counterexample to even j with 15, of all things, so you want an odd j and simplest is to just use floor(M/2) plus 1 if necessary to make it odd. Now take f_1 f_2 = T^2, and check f_1 + T for its gcd with M, as it should have a prime factor of M, for at least one value of f_1, where you iterate through all *integer* solutions to f_1 f_2 = T^2 so you need to consider plus and minus as well as use seemingly trivial possibilities like f_1 = T^2, and f_2 = 1, as well as f_2 = -1. That simple algorithm is to be tested. I have the theory I think worked out, but I keep thinking I have it worked out and then there's some detail that's been missed. Well, it is basic research. James Harris Now that's *really* stupid. How will you know if it works if you don't test it? -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com Stupid? It's your thread adorned with the title you posted. Where does the *real* stupidity reveal itself now? Or does stupidity trump misrepresentation? ...and if not, what then? I thought you said you had the perfect algorithm. But wait, every change you make then establishes a new standard of perfection. Wait and see? Wasn't that the strategy you recently called passive-aggressive? Here's a thought that's better than waiting. Why not simply devise a complete, correct theory and verify it by solving some of the readily accessible challenges? Common sense would affirm that this is an appropriate course of action -- unless you still have something missing, or miswired. You ought to double-check *before* mouthing off. -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com No, that's a rhetorical question. Your claim that the theory was complete is what's stupid. D.8ecio Since you seem reluctant to provide a worked out example, I suppose I will have to try to work one out for myself. To begin with, I'm not even sure from your description what first step such an algorithm would take. Let M = 2180617 m^2 = 4755090500689 Given your equations: yx^2 + Ax - M^2 = 0 yz^2 + Az - j^2 = 0 First question: How are x, y and z choosen? Are they arbitrary? What are the constraints, if any? How are are these constraints to satisfy? How much computation labor is involved in finding suitable values for x, y, and z? What is the algorithm for finding suitable values? Can I simply use x=y=z=1? If not, why not? Your algorithm hasn't given any reason why I cannot use unity for all three values. If you want me to take this seriously at least give me a clue as to what first step I must take to implement the algorithm. --gary shannon Yes I was wondering this too.. In the cases 2y^2 = x_1^2 +x_2^2 4y^2 = x_1^2 +x_2^2+x_3^2 +x_4^2 there are solutions because x_1^2 +x_2^2 and x_1^2 +x_2^2+x_3^2 +x_4^2 are both multiplicative forms i.e. if s_1^2 +s_2^2 = p and t_1^2 +t_2^2 =q there exists u_1,u_2 such that u_1^2 +u_2^2 =pq (s1,s2)(t1,t2) = (s1*t1 -s2*t2, s1*t2+s2*t1) As (1,1) =2, it is just a question of finding (1,1)(a,b)(a,b) = (x1, x2) Similarly with (x1,x2,x3,x4) (1,1,1,1) =4 (s1,s2,s3,s4)(t1,t2,t3,t4) = (s1t1+s2t2+s3t3+s4t4,s1t2 -s2t1+s3t4-s4t3, s1t3-s2t4-s3t1+s4t2, s1t4+s2t3-s3t2-s4t1) So you would have to consider (1,1,1,1)(a,b,c,d)^2 In the cubic case y^3=(x1^3 + x^3 +...+xn^3)/n you would have to look at y^3 =(s1*t1*u1 +s2*t2*u3 + sn*tn*un)/n y^2 =(s1*t1 +s2*t2 + sn*tn)n to get a cubic mutliplicative form. I see but it needs a good biginteger library. If I can improve mine, I would give it try. Try checking between your ears. I'll bet there's something missing there. -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com It is a couple of weeks now since you announced that you have *solved* the factoring problem. You were wrong then, you've been wrong every time you've said it since (as you are still making corrections), so why should anyone listen to you now? You are the boy who cried wolf. Well there are some minor details, like I tried a factorization: M = 77, with j = 75, which gives T = 304 = 16(19) and I find the factorization with f_1 = -8, which gives r = -7 while the second reveals an issue with my technique as 11-1 = 10, but j blocks that, and 11+1 = 12, so j blocks that as it has 15 as a factor. So if f_1 + 1 shares a prime factor with j *and* f_1 - 1 does as well, then that factor will be blocked. The math here is amazingly simple. It's amazing that it could be this easy. Just this little formula Az = (j^2(r+1) - T/(r-1))/r and the derivation is so basic. I wonder about that blocking, maybe it's significant if you have a j that has a lot of prime factors, as if somehow all the prime factors of M plus or minus one share primes with it then the factorization can be blocked. James Harris A sieve is even simpler -- and it works every time! What's really amazing is that you keep pounding on this waste of time and effort. With a little help, B'rer Rabbit got loose from his tar baby. Math is your tar baby, and it appears you are doomed... -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com [JSH] [...] Probably, alas. [JSH] I'm not clear on what your algorithm is now. Is this it? Given odd composite M not the square of a prime: 1. Pick an odd j in 1..M-1. 2. T = M^2 - j^2. 3. For each integer f (positive or negative) dividing T, compute g = gcd(f+1, M). Report that g is a factor if 1 < g < M (gcd in my universe always returns a non-negative result, so in your example above my gcd(-8+1, 77) = 7 and reports success). Right? Wrong? The second what? Perhaps this means that M=7*11, and you found 7 above, so that 11 is the second prime factor of M? If the algorithm above _is_ what you have in mind, here are the troublesome the square of a prime, but the algorithm I gave above-- which may or may not be what you have in mind --doesn't find a factor): M j --- --- 143 141 253 249 299 297 319 315 323 255 377 189 377 375 391 243 403 399 437 219 437 285 437 429 437 435 451 447 481 477 527 459 527 525 533 255 551 3 551 543 559 117 559 507 559 555 589 117 589 255 589 453 589 585 649 645 667 39 667 129 667 561 667 567 667 651 697 309 697 459 703 141 703 429 703 681 703 699 713 129 713 261 713 285 713 291 713 315 713 429 713 549 713 555 713 675 713 699 731 663 731 729 767 765 779 57 779 87 779 195 779 777 803 561 803 801 817 315 817 741 817 771 851 153 851 177 851 285 851 687 851 825 871 195 871 435 893 1 893 201 893 345 893 825 893 891 899 105 899 183 899 303 899 513 899 567 899 603 899 615 899 693 899 825 899 873 899 897 901 833 913 909 923 819 923 921 943 171 943 375 943 405 943 549 943 651 943 939 949 945 979 975 989 15 989 147 989 273 989 315 989 423 989 567 989 825 989 897 989 927 989 975 For M = 112554401 * 221667653, the same implementation has so far tried all odd j in 1 through 5257 without finding a factor. Across 1000 products of two randomly chosen 20-bit primes, and always using j=1, no factors were found. Not any more as I have the full thing now including why you're having problems. It's so simple. It's so hard to believe it's this simple, but it is. That is the basic algorithm, but in any case where f_1 +/- 1 shares a prime factor with j then the factorization is blocked. Solution? Factor Tj^2, and the problem goes away. above, factor. well, this j factors of be troublesome not may not Well that blocking is why, but the solution is easy enough. Yeah, blocking primes, as notice that 141 has 3 as a factor. I'll clip the rest and give you the solution again. You take f_1, where f_1 is a factor of Tj^2, and use f_1 + 1 with the gcd of M. That way also you can use any nonzero j you want, like an even j, and it will factor all of them, as long as j is coprime to M. I prefer not to factor j, which is why techniques I develop won't involve doing so, but if you just want a perfect algorithm to play with, factor it, and see it go. James Harris So simple it is impossible for you to be mistaken Right? (Stay tuned, folks.) -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com [...] [Tim Peters] [JSH] As I said, I tried 1000 products of random 20-bit primes, all with j=1, and none factored. It's obvious that nothing can share a prime factor with j=1, right? As above: factoring Tj^2 is the same as factoring T when j=1. The smallest M that didn't factor at j=1 is 893, as was shown in the table in my original post. Details: M = 893 = 19 * 47 j = 1 T = Tj^2 = M**2 - j**2 = 797448 All integer divisors of T, and the gcd results they lead to: f gcd(f+1, M) ------- ------------------------ 1 gcd(2, 893) = 1 -1 gcd(0, 893) = 893 2 gcd(3, 893) = 1 -2 gcd(-1, 893) = 1 4 gcd(5, 893) = 1 -4 gcd(-3, 893) = 1 8 gcd(9, 893) = 1 -8 gcd(-7, 893) = 1 3 gcd(4, 893) = 1 -3 gcd(-2, 893) = 1 6 gcd(7, 893) = 1 -6 gcd(-5, 893) = 1 12 gcd(13, 893) = 1 -12 gcd(-11, 893) = 1 24 gcd(25, 893) = 1 -24 gcd(-23, 893) = 1 149 gcd(150, 893) = 1 -149 gcd(-148, 893) = 1 298 gcd(299, 893) = 1 -298 gcd(-297, 893) = 1 596 gcd(597, 893) = 1 -596 gcd(-595, 893) = 1 1192 gcd(1193, 893) = 1 -1192 gcd(-1191, 893) = 1 447 gcd(448, 893) = 1 -447 gcd(-446, 893) = 1 894 gcd(895, 893) = 1 -894 gcd(-893, 893) = 893 1788 gcd(1789, 893) = 1 -1788 gcd(-1787, 893) = 1 3576 gcd(3577, 893) = 1 -3576 gcd(-3575, 893) = 1 223 gcd(224, 893) = 1 -223 gcd(-222, 893) = 1 446 gcd(447, 893) = 1 -446 gcd(-445, 893) = 1 892 gcd(893, 893) = 893 -892 gcd(-891, 893) = 1 1784 gcd(1785, 893) = 1 -1784 gcd(-1783, 893) = 1 669 gcd(670, 893) = 1 -669 gcd(-668, 893) = 1 1338 gcd(1339, 893) = 1 -1338 gcd(-1337, 893) = 1 2676 gcd(2677, 893) = 1 -2676 gcd(-2675, 893) = 1 5352 gcd(5353, 893) = 1 -5352 gcd(-5351, 893) = 1 33227 gcd(33228, 893) = 1 -33227 gcd(-33226, 893) = 1 66454 gcd(66455, 893) = 1 -66454 gcd(-66453, 893) = 1 132908 gcd(132909, 893) = 1 -132908 gcd(-132907, 893) = 1 265816 gcd(265817, 893) = 1 -265816 gcd(-265815, 893) = 1 99681 gcd(99682, 893) = 1 -99681 gcd(-99680, 893) = 1 199362 gcd(199363, 893) = 1 -199362 gcd(-199361, 893) = 1 398724 gcd(398725, 893) = 1 -398724 gcd(-398723, 893) = 1 797448 gcd(797449, 893) = 893 -797448 gcd(-797447, 893) = 1 None reveal a factor. [...] See above for the smallest case where that doesn't work with j=1. 1 is coprime to every M. Sorry, test results disagree. Generalizing away from j=1, if the algorithm is: 1. Pick an integer j in 1..M-1. 2. T = M^2 - j^2. 3. For each integer f (positive or negative) dividing Tj^2, compute g = gcd(f+1, M). Report that g is a factor if 1 < g < M. M j ---- ---- 893 1 899 898 1003 1 1073 1 1189 2 1537 1 1537 769 1577 1 1591 1 1643 1 1679 1678 1711 2 1763 86 1843 1 1891 2 2021 1 2077 1 2077 2076 2173 1 2173 1154 2201 2 2257 1 2257 1129 2363 1 2407 2406 2419 2 2449 2 2479 2 For M = 112554401 * 221667653, all j in 1 thru 350 (so far -- program is still running) haven't found a factor. No need to run a test on products of two random 20-bit primes again, because the new algorithm does exactly the same stuff as the old one when j=1. Well, it's simpler now to go back to the derivation to see what's going on. Starting at (r^2 - r)Az = r^2 j^2 - M^2 (r - 1)Az = r j^2 - M^2/r let r = 19, then 18 Az = 19 - 41971 so Az = -6992/3 so for some reason 3 is still a blocking prime. Trying r = -19, gives -20 Az = -19 + 41971 so Az = -10488/5 and this time it's 5. Well, looks like it's time for more theory. I have (r - 1)Az = r j^2 - M^2/r but it's possible to prove that an integer Az that has a single prime factor of M must exist, so let's go find that integer Az. x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az) and focusing on the square root I have sqrt((Az - 2(893^2))^2 - 4(797448)(893)^2) and I want Az to have 19 as a factor, so dividing through by 19, I get sqrt((Az/19 - 2(19)(47^2))^2 - 4(797448)(47)^2) and a solution should be given by Az/19 = 33227 + 53016 + 2(19)(47^2) = 170185 and checking sqrt((170185 - 2(19)(47^2))^2 - 4(797448)(47)^2) = 19789 so I have that Az = 19(170185) now using (r^2 - r)(19)(170185) = r^2 - 797449 which is 3233514 r^2 - 3233515 r + 797449 = 0 so r = ( 3233515 +/- sqrt((3233515)^2 - 4(3233514)(797449))/2(197889) r = (3233515 +/- 375991)/2(197889) r = 1804753/197889 = ( 19 )( 43 )( 47^2 )/( 3 )( 65963 ) or r = 1428762/197889 = ( 2 )( 3 )( 19 )( 83 )( 151 )/( 3 )( 65963 ) so both are fractions, which explains why that particular solution didn't come up. That means my assumption about r being an integer is the one that's suspect. Looking at Az = (j^2(r + 1) - T/(r-1))/r with r a fraction, letting r = n/d, gives Az = (j^2(n + d) - d^2 T/(n-d))/n where n is still a factor of M, but there's that d, which may mean I jumped the gun yet again. Looking at (r - 1)Az = r j^2 - M^2/r the issue has to do with prime factors of r-1 where r-1 is a factor of M, so that's not good. Oh well, time to do more research... James Harris Maybe there are a few more dead raccoons I haven't poked with a stick yet. Anybody got a spare raccoon? -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com Good example, I have a guess. going But notice that 3 IS a factor of T. Well, but 5, isn't, still... But I think that d has prime factors of T, and if so, then it's just back to raising to another power of T, which I don't like. Still if you want to try that guess you'd just use f_1 f_2 = T^3 and check the gcd of f_1 + 1, though I know that's not what it looks like from the equation above, but that's what you can check nonetheless. I'm still thinking about how all this works. If you want more technical information about that guess, well as I've said before I have from the theory that y has prime factors in common with T in its denominator along with the prime factors of M and j, though that has to date not worked out as well as I hoped, and y = (j^2 - Az)/z^2, so substituting gives y = (j^2 (r-1) - r j^2 +- M^2/r)/(r-1)z^2 which indicates that my guess might work. I want to think more about when and how r should be an integer, so I'll just toss that out just in case, while I think more on that. James harris Well, actually it's simpler, and I'm more certain that d is a factor of T, but I'm still thinking about the current argument. In any event, I do know that T/(n-d) must be an integer for some integer d, with n a factor of M. Well, if d is a factor of T, then let d = T/g (I run through a lot of letters so it gets hard to pick), then T/(n-T/g) = gT/(gn-T) so you can iterate through f_1 f_2 = T^2, checking the gcd of f_1 + T against M where if you're wondering why T^2 when I have gT in the numerator, well I don't know what g is, or I could just use it, but I know it's a factor of T, so just using T in place of g covers all the possibilities. If d is a factor of T, then I'm closing in, and that may be it. If d is not a factor of T, then I'm just kind of thinking to myself that I could be at this for a while musing and thinking, wondering about how in the hell you get that variable defined, while things just keep going on like before, and you know? It's kind of frustrating but then again, what else to do? I work this out, and, oh well... James Harris Might as well go find another dead raccoon to poke. -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com I might admit that you're totaly cluless about Mathematics, for instance. Jose Carlos Santos Punch that tar baby a few more times, James. He'll learn to respect you... -- There are two things you must never attempt to prove: the unprovable -- and the obvious. -- Democracy: The triumph of popularity over principle. -- http://www.crbond.com