I was referring to this: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Determinis... which does not involve any randomness whatsoever -- you exhaustively apply Miller-Rabin to all p <= f(N). If you have a modicum of doubt that GRH is true, then use AKS instead: https://en.wikipedia.org/wiki/AKS_primality_test Best wishes, Adam P. Goucher
Sent: Sunday, October 02, 2016 at 11:37 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] The largest twin-primes known today...
That's a philosophically troubling question. Suppose you have a 1000-bit number N and you do a Miller-Rabin check with, say, fifty randomly chosen moduli. (In fact, let's say they are really random, chosen from some natural source like Fourmilab's "hotbits" service.) And say all the checks fail to "witness" that N is composite, so you conclude that N is prime with overwhelming likelihood. Later, some jerk provides an explicit factorization of N.
This is certainly *possible*. There could be, say, N/10 liars among the possible moduli 2 <= a <= N-2. That's a lot of liars, and it's certainly possible that you just had bad luck, with no profound mathematical consequences at all.
On Sun, Oct 2, 2016 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
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 > >> > >
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun