Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: MichaelW on 8 Jun 2010 19:30 On Jun 9, 7:42 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > 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- Hide quoted text - > > - Show quoted text - I politely point out that my algorithm was not meant to be taken seriously (despite the use of JamesSpeak).
From: MichaelW on 8 Jun 2010 19:59 On Jun 9, 12:02 am, JSH <jst...(a)gmail.com> wrote: > 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- Hide quoted text - > > - Show quoted text - Strictly speaking in the post you respond to I don't refer to your work at all so your response is perhaps a bit mis-directed. Also to correct one point the (admitly very silly) MRSA does in fact work for all values of m including m=1. Also it would appear from the responses here that I should have put a smiley face in or something; some posters appear to be taking my algorithm far too seriously. Let us discuss maths. A solution to k^m = q mod N will be in the range of k = {0,1,2...N-1}. Anyone can formualte with a brute force algorithm that comes up with a means of working through the possible solutions. The obvious one is to start from 0 and work through to N-1. Alternately you could do even numbers first and then odd numbers, or in alphabetical order of the english expression of the numbers, or pick out at random (as per MRSA) until you hit a solution. The point is that all of these algorithms are the same thing and are neither unique or useful. In fact they are simply mechanisms for pre-sorting {0,1,2...N-1} before working through the list. Of course they all "work" in the sense that eventually a solution is found but they are not *really* new algorithms. Which brings us to your work. The suspicion is that it is simply another method for picking out solutions. Hence Rotwang's comment in another post: <quote> ....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. </quote> Read my posts carefully. I have *never* formally stated that this is the case for your algorithm. I do suspect that this is the case but I am can be persuaded by *evidence*. It's like the discussion of Mark's text book reference; I made by response on the basis of the evidence. I will not be persuaded by name calling or the amount of work you put in. For this reason I suggest (again) that you pick a reasonably large N (say four digits) and calculate k for each possible value of q. I would suggest m=3 and prime N such that N+1 is divisible by 3. In this case each q will have a unique solution k. Run through the algorithm for each q and total the number of attempts to find k and then take the average and compare it against the average for a brute force approach (roughly N/2). Without this sort of serious evidence you stand exposed to the accusation (however unfair you feel it to be) that your judgement is affected by your emotional commitment to your work. Regards, Michael W.
From: JSH on 8 Jun 2010 20:22 On Jun 8, 4:30 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jun 9, 7:42 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > > > > > > > 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- Hide quoted text - > > > - Show quoted text - > > I politely point out that my algorithm was not meant to be taken > seriously (despite the use of JamesSpeak). The point though is that you put up a random algorithm equivalent to brute force as if it compared to a *derived* result. Your insinuation that maybe the equations I've found are simply brute force is more simply just stated by you versus engaging in...whatever you might call what you did, which I noted as contempt for mathematical process. But even if they are, or are even worse, do you understand why math students still might find them of interest? Let's consider the quadratic case as I give you the benefit of the doubt. f_1 = a_1*k mod N, and f_2 = a_2*k mod N f_1 + f_2 = (a_1 + a_2)*k mod N, so if a_1+a_2 is coprime to N, then k = (f_1+f_2)*(a_1+a_2)^{-1} mod N while f_1*f_2= a_1*a_2*k^2 mod N, so if k^2 = q mod N, you have trivially that f_1*f_2 = a_1*a_2*q mod N. So it is mathematically required that for some T = f_1*f_2 = a_1*a_2*q mod N, you MUST have k, from: k = (f_1+f_2)*(a_1+a_2)^{-1} mod N It's not random. It's absolute in THAT sense, but one can debate over whether or not any particular set of a's will work better than any other, or whether it's still a random process if you have to pick the "right" a's at random, and start finding some T and factoring. But those are mathematical questions that almost immediately do not appear to be trivial. In fact the problem can be approached more closely by looking at explicit equations for the f's, from which one can determine absolutely when this approach will give k. Those equations indicate a density which varies based on a_1, a_2, and k. Trivially you find for instance that if k = floor(N/2), this approach will quickly find solutions with very small values of a_1 and a_2, typically, a_1=a_2 = 1, or a_1 = 1, a_2 = 2. It has other somewhat odd behavior though. For instance if you have q a perfect square such that q = k^2 < N, but k^2 is approximately equal to N, that is a large square near N is q, then this approach find solutions as well with small a's, doing so quickly (may give a very fast square root algorithm in fact). Oh, note that you can find the square root with this approach, so for instance, you can use q=9, and it *may* give you k=3 as a result. That is of interest for many reasons. And that's just some of what can be noted around the quadratic residue result. Fundamental equations in mathematics tend to have infinite amounts of information. That's why they are so prized. A general result of this simplicity in this area is a remarkable find. Modular arithmetic is a jewel of number theory. Your notion above of throwing my result away because you say that it can only have "historical" significance based on the narrow criteria you give reveals mathematical naivette on a maximum scale. Mathematicians do not always just keep the best solution for some algorithm for some practical reason. Mathematics is bigger than that. For insight pick up any number theory journal and note how much in it is NOT practical alongside methods considered more practical. By your criteria the mathematicians who include such results are idiots for so doing. When you think you know better. James Harris
From: MichaelW on 8 Jun 2010 21:04 On Jun 9, 10:22 am, JSH <jst...(a)gmail.com> wrote: > > Trivially you find for instance that if k = floor(N/2), this approach > will quickly find solutions with very small values of a_1 and a_2, > typically, a_1=a_2 = 1, or a_1 = 1, a_2 = 2. > > It has other somewhat odd behavior though. > > For instance if you have q a perfect square such that q = k^2 < N, but > k^2 is approximately equal to N, that is a large square near N is q, > then this approach find solutions as well with small a's, doing so > quickly (may give a very fast square root algorithm in fact). > James, Long post showing you don't understand what you are doing. To pick out an example if a_1 = a_2 = 1 then the solution is obviously f_1= f_2 = k. Your algorithm becomes searching q, q+N, q+2N, q+3N... until you hit k^2. The stuff about square root algorithms does not have a shred of evidence to support it. I asked for evidence and I got an ego trip. Provide evidence. Regards, Michael W.
From: Joshua Cranmer on 8 Jun 2010 21:12
On 06/08/2010 08:22 PM, JSH wrote: > Your insinuation that maybe the equations I've found are simply brute > force is more simply just stated by you versus engaging in...whatever > you might call what you did, which I noted as contempt for > mathematical process. I believe the proper name for the rhetorical device involved is "a parable." -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth |