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

[Georgi Guninski]

On Wed, Sep 30, 2015 at 07:31:34AM -0400, David Wilson wrote:
> 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.


Indeed, a mistake of dumb me (missed the p). Sorry.

> 
> > -----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).
> > 
> >