-----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/
