[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