Full Disclosure mailing list archives
Re: Rapid integer factorization = end of RSA?
From: "e.chukhlomin" <chukh29ru () infoline su>
Date: Sat, 28 Apr 2007 00:08:46 +0400
-----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/
Current thread:
- Re: Rapid integer factorization = end of RSA?, (continued)
- 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? Eugene Chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)