Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: JSH on 8 Jun 2010 10:02 On Jun 8, 1:11 am, MichaelW <ms...(a)tpg.com.au> wrote: > On Tue, 08 Jun 2010 08:10:28 +0000, Tim Little wrote: > > On 2010-06-08, MichaelW <ms...(a)tpg.com.au> wrote: > >> We have k^m = q mod N where m, q and N are given and we wish to solve > >> for k. Let b = the length of the binary representation of N. > > >> Take the binary expansion of pi (fractional part) and take the first b > >> bits as a number and test it as a solution k. If it fails take the next > >> b bits and so on until you get a solution. > > [...] > >> So here is my question: should my algorithm be forgotten by history or > >> recorded forever? > > > It should be recorded forever, next to such well-known algorithms as the > > BogoSort. > > > - Tim > > To be fair the time for the MRSA to solve the equation is of the same > order as sequentially checking 1,2,3... allowing that there is a > theoretical possibility of taking infinite time. Talk about arrogant, readers should note that "MichaelW" is equating whatever he thought up at the moment against a general method for solving for k, when k^m = q mod N, with m a natural number, which is so general it even handles the m=1, as a trivial case, and it works by integer factorization. Said method having been found after years of research on a concept called "surrogate factoring", which asked the question, can you factor one number through factoring another? There is no other known such method in human history, so solving for k otherwise can only be done by brute force. So the uniqueness qualifier is at a maximum. His attempt at dismissal of the result is an expression of contempt for YEARS of basic research and the importance of modular arithmetic in the mathematical world and unfortunately demonstrates a Usenet reality in that posters here can lack even the most basic sense of human decency or respect for the work of others. Students of mathematics are well-advised to steer clear of such behavior, though seeing it in others is a good way to understand how bad it can be with your own results. Don't expect to be cheered. But don't lose heart when jeered. Just look at my example. James Harris
From: dannas on 8 Jun 2010 13:56 "JSH" <jstevh(a)gmail.com> wrote in message news:54b05756-34bc-4041-ada5-2f3c16959b92(a)k25g2000prh.googlegroups.com... On Jun 6, 12:01 pm, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/06/2010 11:26 AM, JSH wrote: > >> > It's zipped at QuarticRes.zip and is a quick and dirty try and just >> > putting something together to try and answer some questions. >> >> Any particular reason you're using Java 1.2 instead of Java 6? >Why not? Hey it works... Java 1.2 is so 1970s, but then you like to stay far behind everybody else >> There are many other comments I could make on your source code... >Geek. (JSH doesn't know java that well)
From: Mark Murray on 8 Jun 2010 16:59 On 07/06/2010 22:00, MichaelW wrote: > I am reading the sections you mention. Whilst it talks around some of > the issues raised my math fu is insufficient to see an exact match. > Are you able to drop a paragraph or two indicating how you would read > the text in the light of the original post? I spent an hour or three putting together a pretty hasty critique of JSH's work. This is by no means worthy of actual publication, and should simply be viewed as rough, preliminary notes scribbled out in LaTeX. Misquotes are all mine. Mistakes are all mine except where they are obviously not. ;-) http://people.freebsd.org:~markm/km_q_modN.pdf Comments, flames, criticism and/or adoring sycophancy welcome in varying degrees. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: Joshua Cranmer on 8 Jun 2010 17:42 On 06/07/2010 11:14 PM, MichaelW wrote: > To put things into perspective here is the Michael Residue Solver > Algorithm. > > We have k^m = q mod N where m, q and N are given and we wish to solve for > k. Let b = the length of the binary representation of N. > > Take the binary expansion of pi (fractional part) and take the first b > bits as a number and test it as a solution k. If it fails take the next b > bits and so on until you get a solution. > > For example let us solve k^3 = 8 mod 29. In this case b is 5 and (using > this site > > http://www.befria.nu/elias/pi/binpi.html > > the first 5 bits of the fractional portion are 00100 = 4; nope. The next > three potential k is 10000 = 16, nope again. The next is k is 11111 = 31 > and 31^3 does indeed equal 8 mod 29! > > So here is my question: should my algorithm be forgotten by history or > recorded forever? It's basically "pick a random valid number and try again until it works", except you explicitly lay out the PRNG algorithm. Given that it is possible to compute any hexadecimal digit in the binary expansion independent of any other hexadecimal digit. It looks like the decimal digits at least pass many randomness tests, but I didn't see any results for anything based on binary expansions. In short: it's not exactly novel just worded in a more unconventional manner, and its "novel" step has little theoretical basis to suggest it is better than it's genesis of an algorithm. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: Rotwang on 8 Jun 2010 18:44
Mark Murray wrote: > On 07/06/2010 22:00, MichaelW wrote: >> I am reading the sections you mention. Whilst it talks around some of >> the issues raised my math fu is insufficient to see an exact match. >> Are you able to drop a paragraph or two indicating how you would read >> the text in the light of the original post? > > I spent an hour or three putting together a pretty hasty critique of > JSH's work. This is by no means worthy of actual publication, and > should simply be viewed as rough, preliminary notes scribbled out in > LaTeX. > > Misquotes are all mine. Mistakes are all mine except where they are > obviously not. ;-) > > http://people.freebsd.org:~markm/km_q_modN.pdf Should be http://people.freebsd.org/~markm/km_q_modN.pdf (forward slash instead of colon) > Comments, flames, criticism and/or adoring sycophancy welcome in > varying degrees. Sorry to say, but I think some of your criticisms miss the mark. For a start, whether or not James knows what an equivalence relation is, he evidently does understand how modular inverses work - quoting from his blog (emphasis added): [...]and the a's are free variables as long as they are non-zero and THEIR SUM IS COPRIME TO N. This guarantees that the required inverse exists, and I think James is vaguely aware that it can be found efficiently. More important, though, is this bit: You don�t pick the a�s, because they are defined in equation (4) where JSH �imagines you have� that which he critically depends on in his derivation. I think you're mistaken about this. The point is, given arbitrary choices of the a's, there exists some T in the equivalence class of a_1*...a_m*q and some factorisation f_1*...*f_m of T such that k can indeed be found by James' formula. This is trivially seen by simply taking f_i = a_i*k and letting T be their product. The problem, as always with his various factoring/residue algorithms, is that you don't know which choice of T, or which of its factorisations, will work unless you already know k. But James is well aware that not every choice works; the only problem is that he's presented no reason to think that the right choice can be found any more efficiently than simply solving the original problem by existing means and reverse-engineering the appropriate choice of T and the f's, and from this point it's classic Harris: as long as he can't see a reason why this /isn't/ more efficient than brute force, it stands to reason in his head that it is. |