[seqfan] Re: Software for searching for Wolstenholme primes?

[David Wilson]

The Granville paper claims evaluating binomial(n,m) (mod p^q) is O(log^2 n + q^4 log n log p + q^4 p log^3 p).
This is not polynomial in log(p), There is a factor p in the last term.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Georgi
> Guninski
> Sent: Tuesday, September 29, 2015 3:41 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Software for searching for Wolstenholme primes?
> 
> On Sun, Nov 18, 2012 at 11:09:02AM -0500, David Wilson wrote:
> > My guess would be probably not.
> >
> > If there were an efficient way to evaluate binomial coefficient
> > residues, then would be an efficient way to evaluate factorial (I
> > think), and we would all be using Wilson's theorem an efficient
> > deterministic primality test.
> >
> 
> For the original old question, check below.
> 
> Computing binomial(n,m) (mod p^q) is polynomial in
> log(n),log(p) and q and in particular efficient.
> 
> See:
> http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf
> 
> Binomial coefficients modulo prime powers
> 
> I don't this gives deterministic primality test, since if $p$ is composite the
> algorithm will return "random" results AFAICT.
> 
> Would be glad if this claim is wrong :)
> 
> Computing binomials modulo composites likely will break factoring.
> 
> (If you expect reply, please CC'me).
> 
> 
> > On 11/17/2012 5:02 AM, Georgi Guninski wrote:
> > >Out of blind opportunism I am looking for efficient software for
> > >verifying if a prime is a  Wolstenholme prime A088164.
> > >
> > >The basic definition requires computing a binomial coefficient mod
> > >p^4.
> > >
> > >For this task found Max Alekseyev's pari binomod.gp, but it appears
> > >slow to me: for p=2124679 binomod took 6 seconds.
> > >
> > >Is there efficient software or references for searching for
> > >Wolstenholme primes?
> > >
> > >_______________________________________________
> > >
> > >Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/