JSH: Posting realities, residues result
in [Math]
|
From: dannas on 11 Jun 2010 17:34 "Joshua Cranmer" <Pidgeot18(a)verizon.invalid> wrote in message news:huu9ds$47$1(a)news-int.gatech.edu... > On 06/11/2010 12:14 PM, Rick Decker wrote: >> As is often the case with your results, all you have done here >> is to invent an obfuscated "test some random values" method. > > To be fair, most factoring methods boil down to "test for one of these > values", but then again, they typically improve on the naive algorithm by > drastically narrowing the search space. > > -- > Beware of bugs in the above code; I have only proved it correct, not tried > it. -- Donald E. Knuth JSH has not excluded even numbers from what I can see.
From: Joshua Cranmer on 11 Jun 2010 17:48 On 06/11/2010 10:13 AM, JSH wrote: > So imagine N = p_1*p_2, so there are *TWO* values for k, given k^2 = q > mod N. If you *picked* k_1 to find q, such that it will tend to be > small, and k_2 is more likely to be selected then the approach I > discovered could conceivably give you k_2, then you have p_1 or p_2 > from (k_2 - k_1) gcd N. Let me get this straight. Your algorithm is essentially: 1. Pick a random number. 2. Construct an equation with this random number which may (must?) have more than one solution. 3. Solve this equation for any solution (which may itself involve another layer of picking numbers; I haven't been paying close attention). 4. If this solution is different, you have the answer. 5. If not, go back to step 1. Wow... in order to trust an algorithm like that, I would need to be given information on why solving a constructed equation would tend to produce a different value than the original equation. Or perhaps I could be swayed if I was shown that the random pick here is more likely to get a value than other, simpler random pick algorithms. > So it's a way to deliberately probe for factors of N, picking k_1 in > order to try and get k_2, which is a technique not available with any > other known method, because no other general way to solve for residues > is known! If so, it's probably because many mathematicians are not avid gamblers. > Human beings are quirky creatures. They can do the damndest things. > So if you're a Usenet poster arguing with people on Usenet the LAST > THING you wish for a target to be, is actually right! The last thing I would wish would be that you were dead. Ergo, you're dead right now, if I'm parsing that sentence correctly. I wonder, what sort of connection speed does the afterlife get? > I'll give the result again, and note that it's trivially derived > though I won't give the derivation again. I'll also note that the > result is basic research so it's not clear how hard it is to get it to > work at any level. The devil is in the details. Well, I know that at least I tend to quickly forget things that aren't useful (e.g., I still cannot code bubblesort, although I can code heapsort). You're basically saying that you're not going to do the hard part of actually making it a worthwhile algorithm. > Now then, back to national security! It IS quite possible that this > information could be of interest to governments, oh, all over the > world. Failure to disclose of it for some of you could be seen as a > LACK OF LOYALTY in your respective countries. Fortunately, I live in a country where lack of loyalty isn't a crime. > Post in reply now with care. No matter how little you think of > Usenet, you can make a decision in this thread which you can't take > back, which will end the life you knew, and move you into a Hell on > earth that you will not escape until you die. I can also make such a decision in real life. Or in Facebook. Or in private email. Or anywhere else on Earth. Your point is? > Kind of like differentiation with the calculus. How big is that? 643241.743 (if you include partial differentiation). -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: JSH on 11 Jun 2010 19:44 On Jun 11, 9:14 am, Rick Decker <rdec...(a)hamilton.edu> wrote: > On 6/11/10 10:13 AM, JSH wrote: > > > I've been fascinated by the response to my posting of a general result > > for solving quadratic residues because of the elephant in the room NOT > > mentioned, which is that it is mod N, whereas mathematicians usually > > MUST use mod p, where p is a prime. > > Oh, really? On what are you basing this observation, pray tell? > > > > > That's important for factoring as if N is a composite then with k^2 = > > q mod N, you have multiple non-trivial solutions for k, where I mean, > > not just k, and N - k, whereas if N=p, then there is only one. > > This has been known for centuries, of course, but thanks for > the heads-up. (BTW, it's not true in general.) > > You might find it helpful to study the Chinese Remainder Theorem. > > > > > And in all the discussion that erupted around my postings on this > > result you may have noticed I noted that the approach tends to prefer > > large k, though all the details of how that works out are not clear > > even to me. > > > So imagine N = p_1*p_2, so there are *TWO* values for k, given k^2 = q > > mod N. If you *picked* k_1 to find q, such that it will tend to be > > small, and k_2 is more likely to be selected then the approach I > > discovered could conceivably give you k_2, then you have p_1 or p_2 > > from (k_2 - k_1) gcd N. > > As is often the case with your results, all you have done here > is to invent an obfuscated "test some random values" method. Here's a direct refutation of the random assertion using more test output from my QuadRes.java program. Readers should note that k = 16016 is also a solution. The program is finding k, such that k^2 = 24025 mod 32033. I found 24025 by squaring floor(32022/2), and taking its residue mod 32033. java QuadRes 24025 32033 k=155 155^2 = 24025 mod 32033 a_1=1, a_2=2 f_1=155, f_2=310 T = 48050 48050 mod 32033 = 16017 Total number of T's used: 3 Total number of factorizations: 11 Individual factors known by program of T that worked: ( 2 )( 5^2 )( 31^2 ) Now then, what is the gcd between 16016 - 155 and 32022? The program sampled 3 T's, and actual tried 11 factorizations of them. That's NOT random. What's weird to me when I do mathematical refutations is how often they are just ignored! And by posters who loudly and proudly proclaim that I'm the one who ignores refutations!!! The best explanation for that behavior is that it's a quirk of the human mind, an ability to reject any and all evidence that a person really does not wish to accept. Math is no exception, despite the ability to provide absolute proof. When faced with absolute proof, some people just absolutely refuse to acknowledge it! Readers can get their own copy of the test program at mymathgroup in the Files section: http://groups.google.com/group/mymathgroup/files?hl=en And again, notice, absolute proof useless with a supposedly mathematical crowd because some posters have decided that mathematics isn't good enough for them--when it's mine. James Harris
From: Joshua Cranmer on 11 Jun 2010 20:23 On 06/11/2010 07:44 PM, JSH wrote: > What's weird to me when I do mathematical refutations is how often > they are just ignored! To paraphrase Dijkstra, examples do not prove a theorem; they can merely disprove one. In this case, you used one case with numbers and absolutely no context to assert that "it's not random." I've generally taken random to mean that the algorithm boils down to "generate a set of candidates and individually try them until one works"; in this context, I suspect there is an implicit added clause that the growth factor of this set is high, like O(pi(n)) or higher. Neither of those definitions have been refuted by your "example." > When faced with absolute proof, some people just absolutely refuse to > acknowledge it! Have you read your supposed definition of mathematical proof? Here it is, quoted directly from your blog: A mathematical proof is a mathematical argument that begins with a truth and proceeds by logical steps to a conclusion which then must be true. Please show me the logical steps in your proof that your algorithm is not random, per either of the definitions of "random" that I gave. If you cannot show me that, then, by your own admission, you do not have a proof, and therefore I have reason to refuse to acknowledge it. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: JSH on 11 Jun 2010 20:58
On Jun 11, 5:23 pm, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/11/2010 07:44 PM, JSH wrote: > > > What's weird to me when I do mathematical refutations is how often > > they are just ignored! > > To paraphrase Dijkstra, examples do not prove a theorem; they can merely > disprove one. You can't disprove a theorem. > In this case, you used one case with numbers and absolutely no context > to assert that "it's not random." I've generally taken random to mean > that the algorithm boils down to "generate a set of candidates and > individually try them until one works"; in this context, I suspect there > is an implicit added clause that the growth factor of this set is high, > like O(pi(n)) or higher. Neither of those definitions have been refuted > by your "example." Well it turns out that for m=2, with small a_1 and a_2, usually 1 and 2, you solve for k, when q = (floor(N/2))^2 mod N. I'll post the example again--which tellingly you deleted out--to correct a mistake I made in a prior post. I actually used (floor(32033/2))^2 mod 32033, not floor(32022/2)^2 mod 32033 as I incorrectly stated in my prior post--probably just a typo which I didn't notice. java QuadRes 24025 32033 k=155 155^2 = 24025 mod 32033 a_1=1, a_2=2 f_1=155, f_2=310 T = 48050 48050 mod 32033 = 16017 Total number of T's used: 3 Total number of factorizations: 11 Individual factors known by program of T that worked: ( 2 )( 5^2 )( 31^2 ) Freaking thing will always exist rapidly as anyone who plays with the program will notice, so they already know you're an idiot if they have. But usually it just gives you back: k = floor(N/2) + 1. I've posted about this before. In this case instead it gives you a k with which you can factor N, demonstrating the potentially SCARY technique which you wish to convince nations around the world--yes, NATIONS would consider it important--is not scary at all, nor potentially dangerous to their national security. Clearly you don't read my posts carefully, but no worries. I usually just skim yours too. Oh, eventually dude you could get a visit from security forces in your country to interview you! Now isn't the anticipation of such an intriguing event exciting? James Harris |