Re: Rapid integer factorization = end of RSA?

[Pavel Kankovsky <peak () argo troja mff cuni cz>]

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/