[seqfan] Re: Software for searching for Wolstenholme primes?
Max Alekseyev
maxale at gmail.com
Wed Sep 30 07:38:38 CEST 2015
I have PARI/GP implementation of computing binomial coefficients modulo
primepowers -- see section III in http://home.gwu.edu/~maxal/gpscripts/
Regards,
Max
On Tue, Sep 29, 2015 at 3:40 AM, Georgi Guninski <guninski at guninski.com>
wrote:
> 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/
>
More information about the SeqFan
mailing list