-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 > Providing the factorization of a particular number (whose > factorization is considered to be not known by anyone) is > definitely a proof that you know the factorization of that number > and that you had a method for finding it. Of course, it doesn't say > anything about this method -- whether it is a general one or > whether you were able to find the factors based on graph of > temperature at the top of Elbrus :-) > > On a more relevant note, let me try to explain the method described > by the original poster, hopefully in a more readable way: > > Take an unknown number N, which we are going to factor. Then, by > some mysterious process, represent the number N, such that (I) N > = A1*B1 + A2*B2 + ... An*Bn AND (II) A1*(N-B1) + A2*(N-B2) + ... + > An*(N-Bn) = N*(q-1) holds. > > In the examples provided by the original poster, these numbers were > always created by taking the usual binary expansion of the number > and splitting each term into a product Ak*Bk. The problem is that > not all (if any) such splits produce the desired results. The > original poster correcly stated that the obvious method for > obtaining such a split (if it really exists under these conditions) > runs in log(N)! steps (that's factorial of log(N), not just an > exclamation... clearly, this number is greater than N, thus > rendering this approach worse than trial division). He also claimed > to have a much faster approach, though. > > Naturally, IF this can be done, one can find q-1 (thus also p,q) > easily. In fact, the "easy" part of the algorithm can be even more > simplified. The sum A1*(N-B1) + A2*(N-B2) + ... An*(N-Bn) can be > rewritten as N*(A1+A2+...+An) - (A1*B1 + A2*B2 + ... An*Bn) = > N*(A1+A2+...+An - 1) and the property (II) tells us that this > number is equal to N*(q-1). In other words, q = (A1+A2+...An), so > -once- we obtain the right sets A,B, finding the factorization is > nothing but summing up a few numbers. > > Now, here are two questions for the original poster: > > 1) Did I understand your factorization "algorithm" correctly? Yes, you are absolutely correct. Regards, Eugene Chukhlomin -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2.2 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGMlhOna5g1zBq1QoRAoSxAKC1A3IjXQBQ+nTHKz75TOyjyXX0LACdGgcx 7Q4hHuxzLmM6QMj2O+lYfss= =rQRk -----END PGP SIGNATURE-----
_______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
