
Re: Factorization theory wrong? Or algorithmic error?
Posted:
Apr 7, 2012 8:09 AM


["FollowupTo:" header set to sci.physics.] On 20120406, Pubkeybreaker <pubkeybreaker@aol.com> wrote: > On Apr 6, 12:49 pm, CWatters <colin.watt...@NOturnersoakSPAM.plus.com> > wrote: >> On 05/04/2012 23:19, barker wrote: >> >> >> >> >> >> > BEGIN PGP SIGNED MESSAGE >> > Hash: SHA512 >> >> > We (mathematicians) have grown to accept the primality checkers as >> > gospel. So did I, until recently. >> >> > This could be big, or it could be I've overlooked something, though I >> > have hunted for 3 days for a flaw. I'd appreciate if you could check >> > this over for me. This post is digitally signed in case I need to prove >> > ownership, should my discovery (if it is a discovery) be stolen. >> >> > As part of my research into improving factorization algorithms, I >> > encountered this composite number, 347 decimal digits long (>1150 bits), >> > which I'll call A: >> >> > 3634908448770161716619462884730373820150226880205007030541419827683585 >> > 7931761274740311086713549497603607279611408949613526779622187756741117 >> > 9048935484829402996681944342388178421558785023331981868685440034884277 >> > 9396792124395994336764804183754455993340622344242614470170379064513230 >> > 0552661368276733695867117608484513671228954258971153834928109857741 >> >> > I won't tell you how I generated A, because if there's no flaw in what >> > I've done (I intend to make real money out of this, if it is possible), >> > the way I came up with A is a giveaway to the whole process. >> >> > I won't ask you to factorize A, because you may not be able to. Here is >> > its "smaller prime factor"** ("B"), which is 156 decimal digits long: >> >> > 3246726736489147307461784686107468324672673648914730746178468610746834 >> > 6821883878114173728372983219193183717113173468218838781141737283729832 >> > 1919318371711317 >> >> > ** that is, smaller as identified by all the factorization algorithms >> > that I have encountered. If you are not professional mathematicians >> > and do not have access to factorization tools, I recommend you use: >> > http://www.alpertron.com.ar/ECM.HTM >> > which will work on any modern web browser, to confirm what I have >> > just stated (i.e., that A is composite, B is prime and that A/B is an >> > integer; whether A/B is prime is moot). >> >> > ECM's author Dario Alpern has diligently implemented factorization >> > algorithms. His implementations are not in question (I assume they are >> > accurate, as do my colleagues)  it is the theory itself that is now >> > in question. >> >> > Divide A by B to get the 192 decimal digit number C. Since 192/2< 156, >> > it follows that if B was the smaller prime factor of A, then C must be >> > prime. >> >> > {Lemma: Assume C was nonprime. Then it must have at least one prime >> > factor that is less than 97 (= 192/2 + 1) decimal digits long. This >> > would falsify the algorithmic result that B, at 156 decimal digits, is >> > the smallest prime factor of A. Therefore C must be prime.} >> >> > I didn't want to give you C (= A/B) as I want you to (trivially) compute >> > it yourself (but for the lazy, it appears at the end of this post). >> >> > Now check C's primality. C should be prime, per the lemma above. Right? >> >> > Indeed, all the primality checkers I have tested show that C is prime. >> > Including the java one at: >> > http://www.alpertron.com.ar/ECM.HTM >> >> > Well, I can tell you that I have factorized C... and handchecked it, as >> > at first I could not believe the fluke finding. >> >> > C's smaller factor is almost 2^300, so C's decomposition is nontrivial. >> > In the time window before you can bruteforce this, I will disclose its >> > factors, and the methods that: >> > 1) got me to A (Hint: diagonalization, Cantor), and >> > 2) factorized C. >> >> > But at this point, I do not want to disclose C's factors, until I have >> > heard the more competent fellow mathematicians here confirm C's alleged >> > primality, according to the algorithms we all becomed conditioned to >> > believing are true. >> >> > I do hope I have not overlooked anything. Your assistance is appreciated. >> >> > Thank you, >> >> > "barker" (associate of the late falsified nondullrich Dr Pertti Lounesto) >> >> > Footnote: For the lazy, here is the 192 decimal digit number C: >> > 1119560943616947347400615409002575284369887465143010602130506309766179 >> > 0753006072671322304202892348769562317880539561982179986874385643005873 >> > 1438452818437316840959014392166803390411010978334873 >> > which tested algorithms suggest is prime, but which I have factorized. >> >> > BEGIN PGP SIGNATURE >> >> > VQEcBAEBCgAGBQJOe7YRAAoJEAjjY4weks8oA7QIAK3ELb/+NKP1vLPT8f7HQTaf >> > YmqnG0TdO44RMJdbqpxsp6DoMx5JkMgluha8y6LIV3rBHHDKGQx3YwKzVTT5r81 >> > DOOQr3LQdLgmoemhdot2Dse16XQ7OoWzvJwqvvYYBZ0S/J2SsrAFUAoQAe35/4 >> > 9NkVg3JSzV+AFPQyv5hpS780v0cObSPl7yz32MypgvZkYZupC3xP/3Pdl8Fg205 >> > NkiDEaDlJcIKM8ARJJtndd7cfNBKZ3Bh1OEQ1NwPFEMZ6uAR3S/DLdF0dY1MMxr >> > RRcluph+MLmTRZngA8NG9qRCBQT2IgTZNatjnZv2pcwgC0MddUnyS07bNypHg8= >> > =87KU >> > END PGP SIGNATURE >> >> For what it's worth a quick cut and paste produced.. >> >> http://www.mathwarehouse.com/arithmetic/numbers/primenumber/primete... >> >> Results of Prime Factorization test >> 111956094361694734740061540900257528436988746514301060213050630976617907530060726713223042028923487695623178805395619821799868743856430058731438452818437316840959014392166803390411010978334873 >> is not a prime number >> >> Obviously if you ask it to look for factors it will time out. Hide quoted text  >> >>  Show quoted text  > > Another lying spammer. www.mathwarehouse.com does not have the > algorithms for even > testing primality of large integers. And the phrase "Prime > Factorization test" is nonsense. > > I have not only tested this with my own software, but also with two > other independent pieces > of software. They all say that it is prime.
I, too, have a homegrown primality prover I wrote a couple of years ago, based on the classical methods ("n1" and "n+1" tests as described near the beginning of Crandall&Pomerance's Primality Proving section). I just ran the number through it and, surprise, it also came out as a proven prime.

