MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Any quantum chemists / physicists?
  • Next by Date: Re: Re: ListCorrelate[] ??
  • Previous by thread: Re: Import a jpg/wmf file
  • Next by thread: matrix columns