Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Factorization theory wrong? Or algorithmic error?
Replies: 44   Last Post: Apr 9, 2012 10:06 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Jan Andres

Posts: 12
Registered: 11/13/11
Re: Factorization theory wrong? Or algorithmic error?
Posted: Apr 7, 2012 8:09 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

["Followup-To:" header set to sci.physics.]
On 2012-04-06, 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 non-prime. 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 hand-checked it, as
>> > at first I could not believe the fluke finding.

>>
>> > C's smaller factor is almost 2^300, so C's decomposition is non-trivial.
>> > In the time window before you can brute-force 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 non-dullrich 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
>> > Ym-qnG0TdO44RMJdbqpxsp6DoMx5JkMgluha8y6LIV3rBHHDKGQx3YwKzVTT5r81
>> > DOOQ-r3LQdLgmoemhdot2Dse16XQ7OoWzvJw-qvvYYBZ0S/J2SsrAFUAoQAe35/4
>> > 9NkVg3-JSzV+AFPQyv5hpS780v0cObSPl7yz32MypgvZkYZupC3xP/3Pdl8Fg205
>> > NkiDEaDl-JcIKM8ARJJtndd7cfNBKZ3Bh1OEQ1NwPFEMZ6uAR3S/DLdF0dY1MMxr
>> > RRcluph+ML-mTRZngA8NG9qRCBQT2IgTZNatjnZv2pcwgC0MddUnyS07bNypHg8=
>> > =87KU
>> > -----END PGP SIGNATURE-----

>>
>> For what it's worth a quick cut and paste produced..
>>
>> http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-te...
>>
>> Results of Prime Factorization test
>> 111956094361694734740061540900257528436988746514301060213050630976617907530­060726713223042028923487695623178805395619821799868743856430058731438452818­437316840959014392166803390411010978334873
>> 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 ("n-1" 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.


Date Subject Author
4/5/12
Read Factorization theory wrong? Or algorithmic error?
barker
4/5/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/5/12
Read Re: Factorization theory wrong? Or algorithmic error?
quasi
4/5/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
barker
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
quasi
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
quasi
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
unruh
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
quasi
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
J. Antonio Perez M.
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
unruh
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
Edward A. Falk
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
rob@robert-earl-hazelett.com
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Jan Andres
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
Edward A. Falk
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
CWatters
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
Jan Andres
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
quasi
4/6/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
hagman
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
hagman
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
barker
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Jan Andres
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pertti's Ghost
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
karl
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pertti's Ghost
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
Richard Tobin
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
unruh
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
J. Antonio Perez M.
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
J. Antonio Perez M.
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
unruh
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pertti's Ghost
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
William Hughes
4/9/12
Read Re: Factorization theory wrong? Or algorithmic error?
karl
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pertti's Ghost
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/8/12
Read Re: Factorization theory wrong? Or algorithmic error?
Pubkeybreaker
4/7/12
Read Re: Factorization theory wrong? Or algorithmic error?
hagman

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.