Documentation patch for mpz_millerrabin

Seth Troisi braintwo at gmail.com
Mon Apr 15 00:11:25 UTC 2019


On Sat, Apr 13, 2019 at 2:30 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il Sab, 13 Aprile 2019 10:55 am, Niels Möller ha scritto:
> > Seth Troisi <braintwo at gmail.com> writes:
>
> >> I see there are some recent changes to mpz_millerrabin around adding
> >> BPSW primality test. I don't think these changes are reflected yet
>
> >> I wrote up what I think is a reasonable explanation of the change
>
> Yes, minimal, but useful.
>
> >> +This function performs some trial divisions, a Baillie-PSW probable
> >> prime
> >> +test, then @var{reps-24} Miller-Rabin probabilistic primality tests.  A
>
> > To make this somewhat bizarre definition make any sense, one probably
> > have to mention that in earlier versions, it used to do reps
> > Miller-Rabin tests.
>
> I agree :-)
>

I reread this twice and understand this now. I've added a note detailing
how this changed in version 6.XX (does anyone know will this be 6.1.3? 6.2?
7?)
New patch is attached, and at
https://github.com/sethtroisi/libgmp/pull/3/files


>
> > "Reasonable values" for @var{reps} also needs some thought. I think
> > passing 24 is reasonable in most cases, one will then rely on BPSW for
> > recent GMP versions, and still use 24 Miller-Rabin iterations with older
> > versions.
>
> Also passing 15 is reasonable, if it was for older versions, it will be
> equivalent to 24 for the jet-to-release version. I'd not touch that
> section.
>
> > Hmm, and now I'm a bit confused, has the new BPSW code been committed
> > yet? In my copy, I see it is used in mini-gmp, but not in
> > mpz/pprime_p.c. And https://gmplib.org/repo/ appears down at the moment
>
> Yes it was committed, but the code was inserted in the millerrabin.c file.
>
changeset:   17704:d417bcef18e6
> date:        Mon Nov 12 23:04:51 2018 +0100
> summary:     mpz/millerrabin.c: Implement BPSW test for primality.
>
> It was also widely tested.
>
> Ĝis,
> m
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 3.patch
Type: text/x-patch
Size: 2869 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190414/e89273f0/attachment.bin>


More information about the gmp-devel mailing list