Hello,
If you have, in fact, come up with a fast method of integer
factorization, the currently unfactored challenges (RSA-704 and above)
would be better proof, no?
no. We're talking about mathemetics, aren't we? So, an example for a
assumption is not a *proof*. Neither are two or three...
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?
2) Could you demonstrate how your algorithm works for the number
2^32+1, please? I have a quite good reason for asking about this
particular number.
Peter
--
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/
