Solving k^m = q mod N
in [Math]
|
Prev: yeah
Next: How small can such a group be?
From: Joshua Cranmer on 8 Jun 2010 23:09 On 06/08/2010 10:44 PM, JSH wrote: > I've been playing with the program for a while and watching some of > the behavior, where yeah, if you put in large squares, less than N-- > especially near N itself, it solves them freaking fast. > > And again, that's just m=2. The result covers m, a Natural number. As Edsger Dijkstra said, "Testing cannot prove the absence of bugs; it can only prove the presence of bugs." Empirical results do not a proof make. How much are you stress testing them? And how fast is `freaking fast'? Did you do comparative performance testing with the brute-force method? Home computers should be able to reach a few hundred to a few thousand MFLOPS on mid-level hardware, so it requires some larger numbers to actually get a good idea. > You're a social animal. You know what people tell you is important. Funny, no one ever told me that memorizing the Periodic Table of Elements was important. Now, if you'll excuse me, I'll just go obtain a bit of element 8 and some element 9 and combine them at 700�C; I don't suppose you'd want a sample of this? -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: JSH on 8 Jun 2010 23:44 On Jun 8, 7:35 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-08, JSH <jst...(a)gmail.com> wrote: > > > 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 > > Why arrogant? What he thought up *is* a general method for solving > for k. Then use it on this example using my approach. java QuadRes 169 177 k=13 13^2 = 169 mod 177 a_1=1, a_2=3 f_1=13, f_2=39 T = 507 T = a_1*a_2*q + 2*N 507 mod 177 = 153 Total number of T's used: 4 Total number of factorizations: 12 Individual factors known by program of T that worked: ( 3 )( 13^2 ) > > Don't expect to be cheered. But don't lose heart when jeered. Just > > look at my example. > > Your example is a good reason *for* losing heart when jeered. If one For you maybe. But you've just been upended. What's your next reply, eh? It should be mathematical. Use the approach you defend with the example I give. > doesn't, one might end up doggedly pursuing obviously worthless > approaches for months at a time, like you. Much of what you call > "jeering" (and ignore) actually contains worthwhile criticism that > could help you. Usually you end up acknowledging that a given > approach is worthless after a couple of months of ignoring people who > are directly showing you why it is worthless, and then rant about how > nobody ever pointed it out. > > As you will again. Welcome to the beginning of your next cycle. > > - Tim Psych-out posts are tedious. My point here is to destroy the mathematical world that was, so that a new one can begin. So yes, "top" mathematicians who may be watching these threads with happiness until now. Your dogs cannot keep you safe for much longer. Psychological warfare will not save you this time. And now ALL that preceded will hit with greater force as those you betrayed most were the students who trusted you. Tossing your asses out of tenure will be a pleasure. James Harris
From: dannas on 9 Jun 2010 00:16 "JSH" <jstevh(a)gmail.com> wrote in message news:5ce0eb63-62d4-421b-afbb-3ef1ea12bc14(a)v12g2000prb.googlegroups.com... On Jun 8, 7:35 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-08, JSH <jst...(a)gmail.com> wrote: > > > 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 > > Why arrogant? What he thought up *is* a general method for solving > for k. Then use it on this example using my approach. <snip math> > > Don't expect to be cheered. But don't lose heart when jeered. Just > > look at my example. > > Your example is a good reason *for* losing heart when jeered. If one For you <snip failed math> > doesn't, one might end up doggedly pursuing obviously worthless > approaches for months at a time, like you. Much of what you call > "jeering" (and ignore) actually contains worthwhile criticism that >> could help you. Usually you end up acknowledging that a given >> approach is worthless after a couple of months of ignoring people who >> are directly showing you why it is worthless, and then rant about how >> nobody ever pointed it out. >> >> As you will again. Welcome to the beginning of your next cycle. >> >> - Tim >My point here is to destroy the mathematical world that was, so that a >new one can begin. Good luck with that one buddy, your failed approach is like watching paint peel on a park bench. >So yes, "top" mathematicians who may be watching these threads with >happiness until now. no, they are doing real pure math, not JSH "Monkey-Math" >And now ALL that preceded will hit with greater force as those you >betrayed most were the students who trusted you. So you failed College Algebra. >Tossing your asses out of tenure will be a pleasure. Yep, you failed it and you are still pissed at them, but you are irrisponcable, time for you JSH to MAN-UP, and accept the Fact that you are just not bright enough for Algebra. >James Harris
From: Mark Murray on 9 Jun 2010 02:46 On 08/06/2010 23:44, Rotwang wrote: >> 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) Oops, thanks! >> 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. Ah - I vaguely thought I may have seen that, but I was working off the ScribD paper which doesn't. Thanks for the correction. http://www.scribd.com/doc/32419109/Beyond-a-Reasonable-Doubt This is the paper that JSH claims to have submitted to Annals. Note that he does not point out that their PRODUCT is coprime to N, which I presume it ought to be. > 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. Thanks! Baby steps, but I'll get there. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: JSH on 9 Jun 2010 10:11
On Jun 8, 8:09 pm, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/08/2010 10:44 PM, JSH wrote: > > > I've been playing with the program for a while and watching some of > > the behavior, where yeah, if you put in large squares, less than N-- > > especially near N itself, it solves them freaking fast. > > > And again, that's just m=2. The result covers m, a Natural number. > > As Edsger Dijkstra said, "Testing cannot prove the absence of bugs; it > can only prove the presence of bugs." Empirical results do not a proof make. The proof is the trivial part. The examples though show that people like you lack credibility. For instance, here's output from my test program again. java QuadRes 4096 4100 k=64 64^2 = 4096 mod 4100 a_1=1, a_2=2 f_1=64, f_2=128 T = 8192 8192 mod 4100 = 4092 Total number of T's used: 1 Total number of factorizations: 6 Individual factors known by program of T that worked: ( 2^13 ) Interested readers can get the program for themselves--in QuadRes.zip-- from the Files section of mymathgroup: http://groups.google.com/group/mymathgroup/files?hl=en That's to show that it cannot just be random. I picked a large square root as intriguingly it handles those, but it's more of a research curiosity than meant to demonstrate practicality. Notice how well that works with one example. > How much are you stress testing them? And how fast is `freaking fast'? Stress testing? Why do that? Example given. > Did you do comparative performance testing with the brute-force method? No. You can do so with the example I give above and post your results!!! > Home computers should be able to reach a few hundred to a few thousand > MFLOPS on mid-level hardware, so it requires some larger numbers to > actually get a good idea. You're a computer geek. Quit playing at being a mathematician on newsgroups. I, at least, acknowledge I'm not one. Posters like you play pretend. Really, I'm serious. I've known for years that a lot of you are computer science nerds but never has it been clearer than with this result that many of you have no clue about mathematical discovery. But you post like you do which is a problem. Fundamental mathematical results can be decades away from concrete pragmatic algorithms that computer geeks understand and like. You're way away from what's familiar to you. Basic research is an unknown to you. James Harris |