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

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/


More information about the SeqFan mailing list