Anyone here who can read/analyze/translate this into English? ------------------------------------------------------------ Date: Thu, 26 Apr 2007 10:53:56 +0400 From: Eugene Chukhlomin <chukh29ru@infoline.su> 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.
At 01:56 AM 4/26/2007, J.A. Terranson wrote:
Anyone here who can read/analyze/translate this into English?
Note the Soviet Union domain name :-) The important sentence is "but exists a short way with fixed complexity for implementation of hypothesis ("plan B") - but, by ethical reason, I'll not post it here." He demonstrates the hard way to do factoring, and says there's an easy method, but isn't willing to explain it. However, if you watch the cards carefully enough, you can see which one has the Red Queen under it, so put your bets on the table. In fact, NP-ishly hard problems do work this way - if you know the answer, you can verify its correctness quickly, so all you need to do is convince the Oracle to let you know the correct answer, but unfortunately it can take an exponentially long period of beseeching before Ms. Pythia will tell you what kind of oil your snake wants.
------------------------------------------------------------ Date: Thu, 26 Apr 2007 10:53:56 +0400 From: Eugene Chukhlomin <chukh29ru@infoline.su> 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. ..... 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
participants (2)
-
Bill Stewart -
J.A. Terranson