c ?
in [Math]
|
Prev: How Can ZFC/PA do much of Math - it Can't Even Prove PA isConsistent(EASY PROOF)
Next: another celebrity goes Scientology
From: master1729 on 3 Jul 2010 03:23 jsh wrote : > I've noted a fundamental result in modular arithmetic > around studying > the simple system of equations: > > f_1 = a_1*k mod N thru f_m = a_m*k mod N > > Specifically by noting that multiplying them together > gives: > > f_1*...*f_m = a_1*...*a_m*k^m mod N, but ADDING them > together gives: > > f_1+...+f_m = (a_1 + ...+ a_m)k mod N > > Note that the a's are what I call control variables, > which can be set > to ANY non-zero value. > > Remarkably enough that simple result allows one to > handle k^m = q mod > N through integer factorization. > > You can solve for k, when m, q and N are known, or > for m, when k, q > and N are known, and it is the latter I'll consider > in more detail in > this post. > > Since the a's are control variables their value can > be set to some > extent, with m degrees of freedom. To handle > discrete logarithms > entirely, over any m, I need to remove less than m of > those degrees > of > freedom and do so with the following equations: > > a_1*...*a_m = q mod N > > and > > a_1+...+a_m = m mod N > > Then k^m = q mod N, and f_1*...*f_m = a_1*...*a_m*k^m > mod N, with > substitutions gives me: > > f_1*...*f_m = q^2 mod N > > and f_1+...+f_m = (a_1 + ...+ a_m)k mod N with > substitution gives: > > f_1+...+f_m = mk mod N > > But so far I've removed only 2 degrees of freedom > from the a's, so > assume that for some unknown number m-c of the f's > that the a's are > simply the modular inverse of k, then for that number > the f's simply > equal 1, giving me: > > f_1+...+f_c + m - c = mk mod N > > Which allows me to solve for m, with: > > m = (k-1)^{-1}(f_1+...+f_c - c) mod N and how do you find c ? > > (If k-1 is not coprime to N, then factors in common > would be divided > off before the modular inverse operation, which > actually gives > another > check for finding useable factors.) > > Notice that finding factors then becomes just a > matter of considering > solutions: > > f_1*...*f_m = q^2 mod N > > where m-c of the factors have been set to 1. > So the reasons for that substitution is clear. > > Notice that c is found dynamically from the count of > non-unit factors > of q^2 mod N. > > Here's an example, solve for m, where: ok , an example , so i can plug in questions. > > 2^m = 13 mod 23 > > so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = > 8 mod 23. > > And I found a solution with f_1*...*f_m = 54, and how did you find 54 ? there are many factorizations of 54 ( mod 23 ) > > f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3 > > so c=4, and how did you find c ? 8 mod 23 = 2*2*2 mod 23 then c = 3 ? > > m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 > = 7 but how did you find c ? > > And 2^7 = 128 = 13 mod 23. > > Notice that the method then gives you the number c > from factoring > numbers q^2 mod N. The means mathematically that c > of the a's have > been set by the algebra itself to cancel out k, with > the modular > inverse, which is how this approach eliminates the > advantage of a > large m--the math simply handles it for you. > > And that is the basic research showing how a simple > set of modular > equations can lead to an approach to solving discrete > logarithms > through integer factorization. It is not clear at > this time how > practical it can be made to be. > > However, I would assume that it is a method that > cannot simply be > ignored as the idiot mutterings of some "crackpot". > But if any of you do, I hope you pay the appropriate > consequences if > it turns out to be important. Paying as high a price > as your world > requires of you. No matter what the price might be. > > > James Harris tommy1729 |