[Gmpcommit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Mar 29 21:10:33 UTC 2015
details: /var/hg/gmp/rev/d4c03ef489ff
changeset: 16563:d4c03ef489ff
user: Torbjorn Granlund <torbjorng at google.com>
date: Sun Mar 29 23:08:54 2015 +0200
description:
Rewrite mpz_probab_prime_p documentation.
details: /var/hg/gmp/rev/ce815aa58777
changeset: 16564:ce815aa58777
user: Torbjorn Granlund <torbjorng at google.com>
date: Sun Mar 29 23:09:57 2015 +0200
description:
ChangeLog
diffstat:
ChangeLog  5 +++++
doc/gmp.texi  22 +++++++++
2 files changed, 14 insertions(+), 13 deletions()
diffs (51 lines):
diff r cbcf1a651748 r ce815aa58777 ChangeLog
 a/ChangeLog Tue Mar 24 17:56:17 2015 +0100
+++ b/ChangeLog Sun Mar 29 23:09:57 2015 +0200
@@ 1,3 +1,8 @@
+20150324 <torbjorng at google.com>
+
+ * mpn/generic/mul_fft.c (mpn_fft_best_k): Don't make pointers `static'
+ just because they point to static (i.e., filelocal) data.
+
20150315 <torbjorng at google.com>
* acinclude.m4 (X86_64_PATTERN): Add CPU code names.
diff r cbcf1a651748 r ce815aa58777 doc/gmp.texi
 a/doc/gmp.texi Tue Mar 24 17:56:17 2015 +0100
+++ b/doc/gmp.texi Sun Mar 29 23:09:57 2015 +0200
@@ 3524,18 +3524,14 @@
@cindex Probable prime testing functions
Determine whether @var{n} is prime. Return 2 if @var{n} is definitely prime,
return 1 if @var{n} is probably prime (without being certain), or return 0 if
 at var{n} is definitely composite.

This function does some trial divisions, then some MillerRabin probabilistic
primality tests. The argument @var{reps} controls how many such tests are
done; a higher value will reduce the chances of a composite being returned as
``probably prime''. 25 is a reasonable number; a composite number will then be
identified as a prime with a probability of less than @m{2^{50},2^(50)}.

MillerRabin and similar tests can be more properly called compositeness
tests. Numbers which fail are known to be composite but those which pass
might be prime or might be composite. Only a few composites pass, hence those
which pass are considered probably prime.
+ at var{n} is definitely nonprime.
+
+This function performs some trial divisions, then @var{reps} MillerRabin
+probabilistic primality tests. A higher @var{reps} value will reduce the
+chances of a nonprime being identified as ``probably prime''. A composite
+number will be identified as a prime with a probability of less than
+ at m{4^{reps},4^( at var{reps})}. Reasonable values of @var{reps} are between 15
+and 50.
@end deftypefun
@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op})
@@ 8852,7 +8848,7 @@
GCD is then implemented as a loop around HGCD, similarly to Lehmer's
algorithm. Where Lehmer repeatedly chops off the top two limbs, calls
@code{mpn_hgcd2}, and applies the resulting matrix to the full numbers, the
subquadratic GCD chops off the most significant third of the limbs (the
+subquadratic GCD chops off the most significant third of the limbs (the
proportion is a tuning parameter, and @math{1/3} seems to be more efficient
than, e.g, @math{1/2}), calls @code{mpn_hgcd}, and applies the resulting
matrix. Once the input numbers are reduced to size below
More information about the gmpcommit
mailing list