Anyone here who can read/analyze/translate this into English?
------------------------------------------------------------
Date: Thu, 26 Apr 2007 10:53:56 +0400
From: Eugene Chukhlomin
To: full-disclosure@lists.grok.org.uk
Subject: [Full-disclosure] Rapid integer factorization = end of RSA?
Hi list!
I discovered a new method of integer factorization for any precision
numbers, probable it should be an end of RSA era.
Details:
Let N - the ring and N = p*q
Then, (-p) in terms of ring(N) is equal (N-p)
Lemma:
p*(-q)=p*q*(-p)
and respective:
(-p)*q=p*q*(-q)
Proof:
p*(-q)=p*(N-q) - by the data, then
p*(-q)=p*(p*q-q)=p*pq-p*q=p*q*p-p*q=(p-1)*(p*q)
(-p)*q=q*(N-p) - by the data, then
(-p)*q=(p*q-p)*q=p*q*q-p*q=p*q*q-p*q=(q-1)*(p*q)
Q. E. D.
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)=p*q*(p-1)
or
A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)
If found such (A1...An) and (B1...Bn), we can find p or q by dividing
p*(q-1) on p*q:
p*(q-1)=p*q*(p-1) => (p*(q-1))/(p*q)=(p-1) => (p-1)+1 = p
or
(p-1)*q=p*q*(q-1)=>((-p)*q)/(p*q)=(q-1) => (q-1)+1 = q
Sample: 21 = 3*7
Let's view a binary representation of this number: 10101 => 2^4 + 2^2 +
1 => 4*4+2*2+1*1
Then, we can try to find 7*(-3) in terms of ring(21):
4*(-4) + 2(-2) + 1*(-1) => 4*(21-4)+2*(21-2)+1*(21-1)=>4*17+2*19+1*20 =
68+38+20=>
68+38+20 = 126 = 6*21
6+1=7
This implementation of my gypothesis has very hard complexity (about a
log2(N)! comparations), but exists a short way with fixed complexity for
implementation of hypothesis ("plan B") - but, by ethical reason, I'll
not post it here.
Regards,
Eugene Chukhlomin
_______________________________________________
--
Yours,
J.A. Terranson
sysadmin@mfn.org
0xBD4A95BF
"The real point is that you cannot harbor malice toward others and then
cry foul when someone displays intolerance against you. Prejudice
tolerated is intolerance encouraged. Rise up in righteousness when you
witness the words and deeds of hate, but only if you are willing to rise
up against them all, including your own. Otherwise suffer the slings and
arrows of disrespect silently."
Harvey Fierstein is an actor and playwright.
