Re: Re: Two factors of (10^71-1)/9 = R71
- To: mathgroup at smc.vnet.net
- Subject: [mg30185] Re: [mg30132] Re: [mg30125] Two factors of (10^71-1)/9 = R71
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 2 Aug 2001 03:15:43 -0400 (EDT)
- References: <200107310827.EAA17537@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
BobHanlon at aol.com wrote: > > In a message dated 2001/7/29 9:42:17 PM, seidovzf at yahoo.com writes: > > >The number William Mopppett wrote: > > ================ > >(10^71 - 1)/9 > >is R71, repunit, number with "all ones". > > > >And it has two factors: > >R71 = > >241573142393627673576957439049 > >*45994811347886846310221728895223034301839 > > > >See, e.g., > >http://www.ping.be/~ping6758/repunits.htm > > > >But suprisingly enough, > >when, before looking for "repunit"s in 37.com, > >I asked my PC to work for saturday, > >its Mathematica session was: > > > > $Version > > 4.0 for Microsoft Windows (December 5, 1999) > > > ><< NumberTheory`FactorIntegerECM` > > > >Timing[f = FactorIntegerECM[(2^128 + 1)/f] ] > >{793.95 Second, 59649589127497217} (* good, but...*) > > > >Timing[FactorIntegerECM[(10^71 - 1)/9 ]] > >{112642. Second, \ > >111111111111111111111111111111111111111111111111111111111111111\ > >11111111} (* ??!! *) > > > >That is Mathematica (or my PC?) considers R71 as prime! > > > >And this is a real suprise > >and hence the question to Mathematica experts: > >how it can be? > > > > R71 = 241573142393627673576957439049* > 45994811347886846310221728895223034301839; > > R71 == (10^71 - 1)/9 > > True > > The documentation for NumberTheory`FactorIntegerECM` states that it extends > Mathematica's integer factoring to all numbers of 40 digits or less. R71 has > 71 digits. It also states that the algorithm returns a single factor (not > necessarily a prime). Mathematica recognizes R71 as non-Prime > > PrimeQ[R71]//Timing > > {0.03333333333284827*Second, False} > > Bob Hanlon > Chantilly, VA USA I cannot comment on NumberTheory`FactorIntegerECM (I simply refuse to try to figure out what it might be doing). It is in an add-on package, so the code is available if anyone wants to take a crack at it. On a different note, we have in our development version an implementation of the multi-polynomial quadratic sieve method of factorization. On a 1000 Mhz machine I get: In[1]:= r71 = (10^71-1)/9; In[2]:= Timing[FactorInteger[r71]] Out[2]= {6572.54 Second, {{241573142393627673576957439049, 1}, {45994811347886846310221728895223034301839, 1}}} In[3]:= FactorInteger[2^128 + 1] // Timing Out[3]= {1.04 Second, {{59649589127497217, 1}, {5704689200685129054721, 1}}} It is quite possible that a good implementation of ecm will beat mpqs on r71, as the smaller factor is 30 digits which is considered within the range of recent implementations of that algorithm. We may tackle that some day. Specifically, David Terr wants to tackle it some day (he did alot of the mpqs implementation, borrowing a small amount of my older code that refused to leave, a holdover from our continued fraction method). But right now we're looking at polynomial algebra improvements and that will take precedence over further integer factorization improvements. Daniel Lichtblau Wolfram Research