Full Disclosure mailing list archives
Re: Rapid integer factorization = end of RSA?
From: Peter Kosinar <goober () ksp sk>
Date: Thu, 26 Apr 2007 22:19:52 +0200 (CEST)
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/
Current thread:
- Re: Rapid integer factorization = end of RSA?, (continued)
- Message not available
- Re: Rapid integer factorization = end of RSA? e.chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Valdis . Kletnieks (Apr 26)
- Re: Rapid integer factorization = end of RSA? Pavel Kankovsky (Apr 27)
- Message not available
- Re: Rapid integer factorization = end of RSA? Eugene Chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)
- Re: Rapid integer factorization = end of RSA? virus (Apr 26)
- Re: Rapid integer factorization = end of RSA? Brendan Dolan-Gavitt (Apr 26)
- Re: Rapid integer factorization = end of RSA? virus (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stephan Gammeter (Apr 26)
- Re: Rapid integer factorization = end of RSA? ShadowGamers (Apr 26)
- Re: Rapid integer factorization = end of RSA? Peter Kosinar (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)