So an "unlucky" Miller-Rabin case would refute GRH? --rwg On 2016-10-02 02:50, Adam P. Goucher wrote:
On 2016-09-21 04:29, Adam P. Goucher wrote:
I personally like Pollard's rho factorisation. Easy to implement (no fancy sieves) and offers a quadratic speedup over trial division (so a worst-case time complexity of sqrt(sqrt(N)) for factorising N).
It's easy to like: fast, terse, and clever. But it just finds a factor rather than the full factorization, and doesn't prove primality. How tersely can we do *all* this if we settle for √n time complexity? --rwg
You can check primality first using Miller-Rabin for various initial values. I think there's a bound (or rather two, the tighter one being dependent on GRH) of how many values you need to check.
Sent: Wednesday, September 21, 2016 at 1:20 PM From: "Bill Gosper" <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] The largest twin-primes known today...
On Wed, Sep 21, 2016 at 2:14 AM, Bill Gosper <billgosper@gmail.com> wrote:
I think Allan means 3^2, not 3^12. This would have been an extremely easy factorization even for Lehmer's optical contraption <https://en.wikipedia.org/wiki/Lehmer_sieve>. Or Macsyma back when it trial-divided by consecutive odd numbers. Which is pretty much like GCDing with their product, now that we can store big numbers. I just wrote a tiny (and very untested) recursive program in a similar vein:
In[832]:= Clear[dumfac]; dumfac@1 = {}; dumfac[n_Integer] := (dumfac@n = {n}; dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ GCD[n, Binomial[#, Floor[#/2]] &@Floor[Sqrt[n]]])
In[833]:= dumfac[2996863034895] // tim
During evaluation of In[833]:= 0.188517 sec, 5
Out[833]= {5, 3, 3, 18583, 3583757}
In[834]:= PrimeQ /@ %
Out[834]= {True, True, True, True, True} --rwg
Phew, that doesn't even slightly work!
In[342]:= dumfac@11111111111111111 // tim
During evaluation of In[342]:= 12.903538,1
Out[342]= {11111111111111111}
Mindlessly changing a 2 to a 3, In[338]:= Clear[dumfac]; dumfac@1 = {}; dumfac[n_Integer] := (dumfac@n = {n}; dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ GCD[n, Binomial[#, Floor[#/3]] &@Floor[Power[n, (2)^-1]]])
In[339]:= dumfac@11111111111111111 // tim
During evaluation of In[339]:= 11.772568,2
Out[339]= {2071723, 5363222357}
But 12 seconds! On 2016-09-21 03:04, Tom Karzes wrote:
Or you could just invoke the factor program that's part of GNU coreutils and is part of a standard Ubuntu Linux install:
% factor 2996863034895 2996863034895: 3 3 5 18583 3583757 %
See the info file for details.
Tom
But the elephant in the room is Mathematica: In[320]:= FactorInteger[(10^59 - 1)/9] // tim
During evaluation of In[320]:= 0.035899 sec, 2
Out[320]= {{2559647034361, 1}, {4340876285657460212144534289928559826755746751, 1}} --rwg
On 2016-09-20 16:05, Allan Wechsler wrote:
Factoris says the coefficient factors to 3^12.5.18583.3583757.
On Tue, Sep 20, 2016 at 6:55 PM, Dan Asimov <asimov@msri.org>
wrote:
> P.S. I'm puzzled by this statement about these twin primes at
that link:
> > ----- > They will enter Chris Caldwell's “The Largest Known Primes Database” > (http://primes.utm.edu/primes) ranked 1st for twins, and each entered > individually ranked 4180th overall. > ----- > > Why do they have the same ranking overall? Does it not matter that > one is bigger than the other? > > —Dan > > > > On Sep 20, 2016, at 3:35 PM, Dan Asimov <asimov@msri.org> wrote: > > > > Is anything known about the factorization of that coefficient > > > > (other than its divisibility by 5 and 9)? > > > > Was it chosen as part of some algorithm that singled out relatively > > likely candidates? Or was it just stumbled on at random from a > > massive search? > > > > > > Or maybe one of our factoring experts can factor it? (You know who you > are.) > > > > —Dan > > > > > >> On Sep 20, 2016, at 3:18 PM, Eric Angelini < Eric.Angelini@kntv.be
> wrote: > >> > >> > >> ... are: > >> 2996863034895*2^1290000-1 > >> and > >> 2996863034895*2^1290000+1 > >> > >> http://www.primegrid.com/download/twin-1290000.pdf >