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

Georgi Guninski guninski at guninski.com
Tue Sep 29 09:40:32 CEST 2015

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.


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/

More information about the SeqFan mailing list