Full Disclosure mailing list archives
Re: Rapid integer factorization = end of RSA?
From: Pavel Kankovsky <peak () argo troja mff cuni cz>
Date: Fri, 27 Apr 2007 20:42:16 +0200 (MET DST)
On Thu, 26 Apr 2007, e.chukhlomin wrote:
Gypothesis: Let N = p*q = A1*B1 + A2*B2... + An*Bn Then exists some subset(A1...An) and respective subset(B1...Bn), which satisfies for equality: A1*B1+A2*B2...+An*Bn = p*q and: A1*(-B1)+A2*(-B2)...+An*(-Bn) = p*(-q)=p*q*(p-1) or A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)
Let n = 1, A1 = p, B1 = q. Then 1. A1B1 = pq = N. 2. A1(-B1) = p(-q) = [let's pretend this careless mixing of equalities in Z an congruences in Z_N makes any sense and assume -X stands for N-X] = p(N-q) = p(pq-q) = p(p-1)q = pq(p-1). QED. Ok. Your "gypothesis" holds (sort of). We can factor N when we know its factors. What a breakthrough. Perhaps Bill Gates will mention it in "The Road Ahead II". --Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] "Resistance is futile. Open your source code and prepare for assimilation." _______________________________________________ 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:
- 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? Kurt Buff (Apr 26)
- 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)
- Re: Rapid integer factorization = end of RSA? e.chukhlomin (Apr 26)
- <Possible follow-ups>
- 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)