Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Hello, Peter Kosinar wrote: > 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 agreed. > 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 :-) Right, giving an example doesn't proof the method. That's what I was talking about. But it seems some participants of the list don't understand how to proof something in mathematics and take an example as a proof for a method. GTi ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
-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/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
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/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Hello, >> If you have, in fact, come up with a fast method of integer >> factorization, the currently unfactored challenges (RSA-704 and above) >> would be better proof, no? > > no. We're talking about mathemetics, aren't we? So, an example for a > assumption is not a *proof*. Neither are two or three... 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? 2) Could you demonstrate how your algorithm works for the number 2^32+1, please? I have a quite good reason for asking about this particular number. Peter -- [Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278 ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
On Thu, 26 Apr 2007 22:31:08 +0400, "e.chukhlomin" said: > More over, while no one present valid proof of incorrectness, it is > correct, right? "Beware bugs in the above code; I have only proven it correct, not tested it." -- famous quiche-eater Don Knuth pgpq61YbrtJkV.pgp Description: 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/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
xxx xxx wrote: > > 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. > > > Like Stanislaw said before be, this Lemma is obvious. You're > saying that 0=0, and man, this is a thautology! > You ask why? let N = p*q. > Then, > p*q = 0 mod N > Now, let be -1 the opposite of the unit ( usually called e...) > 0 = (-1)*0 = (-1)*p*q = (-1*p)*q = (-p)*q > 0 = 0*(-q) = p*q*(-q) > > 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) > > > This is another obvious thing! > if N = sum(A_i*B_i), then > -N = -1*N = -1*sum(A_i*B_i) = 0 mod N > and, for the distributive propeties, > -1*sum(A_i*B_i) = sum (-1*A_i*B_i) = 0 mod N > > > 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 > > > Here there's a mistake: p*(q-1) != p*q*(p-1) mod N. in fact, let N = > 2*3. > 2*2 = 4 ! = 6*1 = 0!!! > Beeing this assumption wrong, all the remaining demostration is > obviously false... > ok, if your consequences are right, could you disprove this gypothesis? 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) in terms of this gypothesis, could you really prove: there are no one subsets (A1..An) and respective (B1...Bn) which satisfies 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) ? Another example in terms of gypothesis: 35 = 2^2*2^3 + 2*1 + 1 then one of possible subsets of 35 is: 4*8 + 2*1 + 1 (4,2,1) and (8,1,1) try one of possible cases for test subsets (A1...An) and (B1...Bn): 4*(35-8)+2*(35-1)+1*(-1) = 4*27 + 2*34 + 1*(34) = 108 + 102 = 210 then, 210 / 35 = 6 6+1=7 gcd(35,7)=5 Gypothesis is right (or written above is exception?) Your sample: 6 = 4 + 2 => 1*4 + 2*1 1*(6-4)+2*(6-1)=12 Divide result by 6: 12/6 = 2 Add one for 2: 2+1 = 3 Test: gcd(6,3)=2 Any other samples needed? More over, while no one present valid proof of incorrectness, it is correct, right? Has somebody more constructive ideas? ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Spamtastic you say? GODWIN'S LAW GET? ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
[EMAIL PROTECTED] schrieb: > Hello, > > Brendan Dolan-Gavitt wrote: > >> If you have, in fact, come up with a fast method of integer >> factorization, the currently unfactored challenges (RSA-704 and above) >> would be better proof, no? >> > > no. We're talking about mathemetics, aren't we? So, an example for a > assumption is not a *proof*. Neither are two or three... > > >> Are you by any chance related to James Harris? >> > > Nope. Trying to prove Fermat's theorem is not from interest for me :) > > GTi > > ___ > Full-Disclosure - We believe in it. > Charter: http://lists.grok.org.uk/full-disclosure-charter.html > Hosted and sponsored by Secunia - http://secunia.com/ > > Just factor a damn RSA-Challenge, then we'll believe you without seeing an actual proof. If not, you're just waisting our time with spamtastic entertainment. ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Get it peer-reviewed, or go away.
On 4/25/07, Eugene Chukhlomin <[EMAIL PROTECTED]> wrote:
> 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
>
> ___
> Full-Disclosure - We believe in it.
> Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/
>
___
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Hello, Brendan Dolan-Gavitt wrote: > If you have, in fact, come up with a fast method of integer > factorization, the currently unfactored challenges (RSA-704 and above) > would be better proof, no? no. We're talking about mathemetics, aren't we? So, an example for a assumption is not a *proof*. Neither are two or three... > Are you by any chance related to James Harris? Nope. Trying to prove Fermat's theorem is not from interest for me :) GTi ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
If you have, in fact, come up with a fast method of integer factorization, the currently unfactored challenges (RSA-704 and above) would be better proof, no? Are you by any chance related to James Harris? http://www.crank.net/harris.html -Brendan On 4/26/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > Hello, > > Eugene Chukhlomin wrote: > > Well, let's proof: some days ago RSA-640 was factored, therefore I'll > > use this number for proofing. > > N = p*q = 3107418240490043721... [...] Q.E.D > > that's an example. Not a *proof*. > > GTi > > ___ > Full-Disclosure - We believe in it. > Charter: http://lists.grok.org.uk/full-disclosure-charter.html > Hosted and sponsored by Secunia - http://secunia.com/ > ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
Hello, Eugene Chukhlomin wrote: > Well, let's proof: some days ago RSA-640 was factored, therefore I'll > use this number for proofing. > N = p*q = 3107418240490043721... [...] Q.E.D that's an example. Not a *proof*. GTi ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
On Thu, Apr 26, 2007 at 03:04:39PM +0400, Eugene Chukhlomin wrote: > >#v+ > >gap> p; > >163473364580925384844313388386509085984178367003309231218111085238933310010450\ > >8151212118167511579 > >gap> q; > >19008712816648221131268515739354139754718967899685154933853908802710380210\ > >4498957191261465571 > >gap> n := p * q; > >310741824049004372135075003588856793003734602284272754572016194882320644051808\ > >150455634682967172328678243791627283803341547107310850191954852900733772482278\ > >3525742386454014691736602477652346609 > >gap> (p * (n - q)) mod n; > >0 > >gap> > >#v- > > > >What is it supposed to proove? > > > > My gypothesis: if exists subsets(A1...An) and (B1...Bn) which satisfies > equality: A1*B1 +...An*Bn = N = p*q, then exists some of them, which > satisfies equality A1*(-B1)+...An*(-Bn)=p*q*(q-1) But what does that proof have to do with your gypothesis? Except that p*q * (q-1) = p*q = p*q * (-1) = p*q * (N-1) = 0 (mod N) what is obvious equality. -- Stanislaw Klekot ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
>#v+ >gap> p; >163473364580925384844313388386509085984178367003309231218111085238933310010450\ >8151212118167511579 >gap> q; >19008712816648221131268515739354139754718967899685154933853908802710380210\ >4498957191261465571 >gap> n := p * q; >310741824049004372135075003588856793003734602284272754572016194882320644051808\ >150455634682967172328678243791627283803341547107310850191954852900733772482278\ >3525742386454014691736602477652346609 >gap> (p * (n - q)) mod n; >0 >gap> >#v- > >What is it supposed to proove? My gypothesis: if exists subsets(A1...An) and (B1...Bn) which satisfies equality: A1*B1 +...An*Bn = N = p*q, then exists some of them, which satisfies equality A1*(-B1)+...An*(-Bn)=p*q*(q-1) ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
On Thu, Apr 26, 2007 at 02:07:31PM +0400, Eugene Chukhlomin wrote: > >Funny way to pull the -1 out from the parenthesis. > >p * (-q) = p * (-1) * q = p * q * (-1) (mod pq) > >That is, p * (-q) = 0 (mod pq). > > Well, let's proof: > some days ago RSA-640 was factored, therefore I'll use this number for > proofing. > N = p*q = > 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 > > p = > 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 > q = > 190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571 > > Hence p*(-q) = p*(N-q), we have: > 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579*(3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609-190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571) > = > 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002; > > and, by my gypothesis: > p*(-q) = p*q *(p-1) = p*(N-q) > 163473364580925384844313388386509085984178363092312181110852389333100104508151212118167511579*190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571*1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511578 > = > 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002; > Q.E.D Of course it's equal. And equal to zero modulo n, as I pointed. #v+ gap> p; 163473364580925384844313388386509085984178367003309231218111085238933310010450\ 8151212118167511579 gap> q; 19008712816648221131268515739354139754718967899685154933853908802710380210\ 4498957191261465571 gap> n := p * q; 310741824049004372135075003588856793003734602284272754572016194882320644051808\ 150455634682967172328678243791627283803341547107310850191954852900733772482278\ 3525742386454014691736602477652346609 gap> (p * (n - q)) mod n; 0 gap> #v- What is it supposed to proove? -- Stanislaw Klekot ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
>Funny way to pull the -1 out from the parenthesis. >p * (-q) = p * (-1) * q = p * q * (-1) (mod pq) >That is, p * (-q) = 0 (mod pq). Well, let's proof: some days ago RSA-640 was factored, therefore I'll use this number for proofing. N = p*q = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 p = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 q = 190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571 Hence p*(-q) = p*(N-q), we have: 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579*(3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609-190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571) = 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002; and, by my gypothesis: p*(-q) = p*q *(p-1) = p*(N-q) 163473364580925384844313388386509085984178363092312181110852389333100104508151212118167511579*190087128166482211312685157393541397547189678996851549338539088027103802104498957191261465571*1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511578 = 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002; Q.E.D Any new idea? ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] Rapid integer factorization = end of RSA?
On Thu, Apr 26, 2007 at 10:53:56AM +0400, Eugene Chukhlomin wrote:
> 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.
Funny way to pull the -1 out from the parenthesis.
p * (-q) = p * (-1) * q = p * q * (-1) (mod pq)
That is, p * (-q) = 0 (mod pq).
> 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)
For example, whole A_k and B_k, k = {1..n} sets? Second and third
expressions in both lines are congruent to 0 mod pq.
> 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
^
This is untrue.
p * (q - 1) = p * q - p = -p != 0 (mod pq)
p * q * (p - 1) = 0 * (p - 1) = 0 (mod pq)
> p*(q-1)=p*q*(p-1) => (p*(q-1))/(p*q)=(p-1) => (p-1)+1 = p
^^^
Dividing by zero in _any ring_ is illegal.
By the way, if you find x = p * (q - 1) you can use Euclidean algorithm
to find GCD(x, pq). Since GCD(q - 1, q) = 1, you get GCD(x, p), and that
would be p as p divides x.
> 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
OK, but where did you get 7 and -3 (from underscored expression) from?
3*7 is public, but both 3 and 7, as elements of multiplication, are
private. And if you get (7, -3) pair, why didn't you simply multiplicate
the second element of this pair by -1?
> 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
--
Stanislaw Klekot
___
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/
[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
___
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/
