[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Nov 10 13:23:29 UTC 2018
details: /var/hg/gmp/rev/aed6e4a7df09
changeset: 17684:aed6e4a7df09
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Sat Nov 10 14:07:27 2018 +0100
description:
mpz/lucmod.c: New file, Lucas' sequence modulo m
details: /var/hg/gmp/rev/94b7b61a3ff0
changeset: 17685:94b7b61a3ff0
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Sat Nov 10 14:13:27 2018 +0100
description:
tests/mpz/t-lucm.c: New test, for the internal function mpz_lucas_mod
diffstat:
Makefile.am | 2 +-
gmp-impl.h | 3 +
mpz/Makefile.am | 2 +-
mpz/lucmod.c | 127 ++++++++++++++++++++++++++++++++++++++++++++
tests/mpz/Makefile.am | 2 +-
tests/mpz/t-lucm.c | 144 ++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 277 insertions(+), 3 deletions(-)
diffs (truncated from 328 to 300 lines):
diff -r 395fb75310ab -r 94b7b61a3ff0 Makefile.am
--- a/Makefile.am Thu Nov 08 19:22:54 2018 +0100
+++ b/Makefile.am Sat Nov 10 14:13:27 2018 +0100
@@ -196,7 +196,7 @@
mpz/kronuz$U.lo mpz/kronzs$U.lo mpz/kronzu$U.lo \
mpz/lcm$U.lo mpz/lcm_ui$U.lo mpz/limbs_finish$U.lo \
mpz/limbs_modify$U.lo mpz/limbs_read$U.lo mpz/limbs_write$U.lo \
- mpz/lucnum_ui$U.lo mpz/lucnum2_ui$U.lo \
+ mpz/lucmod$U.lo mpz/lucnum_ui$U.lo mpz/lucnum2_ui$U.lo \
mpz/millerrabin$U.lo mpz/mod$U.lo mpz/mul$U.lo mpz/mul_2exp$U.lo \
mpz/mul_si$U.lo mpz/mul_ui$U.lo \
mpz/n_pow_ui$U.lo mpz/neg$U.lo mpz/nextprime$U.lo \
diff -r 395fb75310ab -r 94b7b61a3ff0 gmp-impl.h
--- a/gmp-impl.h Thu Nov 08 19:22:54 2018 +0100
+++ b/gmp-impl.h Sat Nov 10 14:13:27 2018 +0100
@@ -1704,6 +1704,9 @@
#define mpz_oddfac_1 __gmpz_oddfac_1
__GMP_DECLSPEC void mpz_oddfac_1 (mpz_ptr, mp_limb_t, unsigned);
+#define mpz_lucas_mod __gmpz_lucas_mod
+__GMP_DECLSPEC int mpz_lucas_mod (mpz_ptr, mpz_ptr, long, mp_bitcnt_t, mpz_srcptr, mpz_ptr, mpz_ptr);
+
#define mpz_inp_str_nowhite __gmpz_inp_str_nowhite
#ifdef _GMP_H_HAVE_FILE
__GMP_DECLSPEC size_t mpz_inp_str_nowhite (mpz_ptr, FILE *, int, int, size_t);
diff -r 395fb75310ab -r 94b7b61a3ff0 mpz/Makefile.am
--- a/mpz/Makefile.am Thu Nov 08 19:22:54 2018 +0100
+++ b/mpz/Makefile.am Sat Nov 10 14:13:27 2018 +0100
@@ -54,7 +54,7 @@
invert.c ior.c iset.c iset_d.c iset_si.c iset_str.c iset_ui.c \
jacobi.c kronsz.c kronuz.c kronzs.c kronzu.c \
lcm.c lcm_ui.c limbs_read.c limbs_write.c limbs_modify.c limbs_finish.c \
- lucnum_ui.c lucnum2_ui.c mfac_uiui.c millerrabin.c \
+ lucnum_ui.c lucnum2_ui.c lucmod.c mfac_uiui.c millerrabin.c \
mod.c mul.c mul_2exp.c mul_si.c mul_ui.c n_pow_ui.c neg.c nextprime.c \
oddfac_1.c \
out_raw.c out_str.c perfpow.c perfsqr.c popcount.c pow_ui.c powm.c \
diff -r 395fb75310ab -r 94b7b61a3ff0 mpz/lucmod.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpz/lucmod.c Sat Nov 10 14:13:27 2018 +0100
@@ -0,0 +1,127 @@
+/* mpz_lucas_mod -- Helper function for the strong Lucas
+ primality test.
+
+ THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST
+ CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
+ FUTURE GNU MP RELEASES.
+
+Copyright 2018 Free Software Foundation, Inc.
+
+Contributed by Marco Bodrato.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+or
+
+ * the GNU General Public License as published by the Free Software
+ Foundation; either version 2 of the License, or (at your option) any
+ later version.
+
+or both in parallel, as here.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received copies of the GNU General Public License and the
+GNU Lesser General Public License along with the GNU MP Library. If not,
+see https://www.gnu.org/licenses/. */
+
+#include "gmp-impl.h"
+
+/* Computes V_{k+1}, Q^{k+1} (mod n) for the Lucas' sequence */
+/* with P=1, Q=Q; k = n>>b0. */
+/* Requires n > 4; b0 > 0; -2*Q must not overflow a long. */
+/* If U_{k+1}==0 (mod n) or V_{k+1}==0 (mod n), it returns 1, */
+/* otherwise it returns 0 and sets V=V_{k+1} and Qk=Q^{k+1}. */
+/* V will never grove beyond SIZ(n), Qk not beyon 2*SIZ(n). */
+int
+mpz_lucas_mod (mpz_ptr V, mpz_ptr Qk, long Q,
+ mp_bitcnt_t b0, mpz_srcptr n, mpz_ptr T1, mpz_ptr T2)
+{
+ mp_bitcnt_t bs;
+ int res;
+
+ ASSERT (b0 > 0);
+ ASSERT (SIZ (n) > 1 || SIZ (n) > 0 && PTR (n) [0] > 4);
+
+ mpz_set_ui (V, 1); /* U1 = 1 */
+ bs = mpz_sizeinbase (n, 2) - 2;
+ if (UNLIKELY (bs < b0))
+ {
+ /* n = 2^b0 - 1, should we use Lucas-Lehmer instead? */
+ ASSERT (bs == b0 - 2);
+ mpz_set_si (Qk, Q);
+ return 0;
+ }
+ mpz_set_ui (Qk, 1); /* U2 = 1 */
+
+ do
+ {
+ /* We use the iteration suggested in "Elementary Number Theory" */
+ /* by Peter Hackman (November 1, 2009), section "L.XVII Scalar */
+ /* Formulas", from http://hackmat.se/kurser/TATM54/booktot.pdf */
+ /* U_{2k} = 2*U_{k+1}*U_k - P*U_k^2 */
+ /* U_{2k+1} = U_{k+1}^2 - Q*U_k^2 */
+ /* U_{2k+2} = P*U_{k+1}^2 - 2*Q*U_{k+1}*U_k */
+ /* We note that U_{2k+2} = P*U_{2k+1} - Q*U_{2k} */
+ /* The formulas are specialized for P=1, and only squares: */
+ /* U_{2k} = U_{k+1}^2 - |U_{k+1} - U_k|^2 */
+ /* U_{2k+1} = U_{k+1}^2 - Q*U_k^2 */
+ /* U_{2k+2} = U_{2k+1} - Q*U_{2k} */
+ mpz_mul (T1, Qk, Qk); /* U_{k+1}^2 */
+ mpz_sub (Qk, V, Qk); /* |U_{k+1} - U_k| */
+ mpz_mul (T2, Qk, Qk); /* |U_{k+1} - U_k|^2 */
+ mpz_mul (Qk, V, V); /* U_k^2 */
+ mpz_sub (T2, T1, T2); /* U_{k+1}^2 - (U_{k+1} - U_k)^2 */
+ if (Q > 0) /* U_{k+1}^2 - Q U_k^2 = U_{2k+1} */
+ mpz_submul_ui (T1, Qk, Q);
+ else
+ mpz_addmul_ui (T1, Qk, NEG_CAST (unsigned long, Q));
+
+ /* A step k->k+1 is performed if the bit in $n$ is 1 */
+ if (mpz_tstbit (n, bs))
+ {
+ /* U_{2k+2} = U_{2k+1} - Q*U_{2k} */
+ mpz_mul_si (T2, T2, Q);
+ mpz_sub (T2, T1, T2);
+ mpz_swap (T1, T2);
+ }
+ mpz_tdiv_r (Qk, T1, n);
+ mpz_tdiv_r (V, T2, n);
+ } while (--bs >= b0);
+
+ res = SIZ (Qk) == 0;
+ if (!res) {
+ mpz_mul_si (T1, V, -2*Q);
+ mpz_add (T1, Qk, T1); /* V_k = U_k - 2Q*U_{k-1} */
+ mpz_tdiv_r (V, T1, n);
+ res = SIZ (V) == 0;
+ if (!res && b0 > 1) {
+ /* V_k and Q^k will be needed for further check, compute them. */
+ /* FIXME: Here we compute V_k^2 and store V_k, but the former */
+ /* will be recomputed by the calling function, shoul we store */
+ /* that instead? */
+ mpz_mul (T2, T1, T1); /* V_k^2 */
+ mpz_mul (T1, Qk, Qk); /* P^2 U_k^2 = U_k^2 */
+ mpz_sub (T2, T2, T1);
+ ASSERT (SIZ (T2) == 0 || PTR (T2) [0] % 4 == 0);
+ mpz_tdiv_q_2exp (T2, T2, 2); /* (V_k^2 - P^2 U_k^2) / 4 */
+ if (Q > 0) /* (V_k^2 - (P^2 -4Q) U_k^2) / 4 = Q^k */
+ mpz_addmul_ui (T2, T1, Q);
+ else
+ mpz_submul_ui (T2, T1, NEG_CAST (unsigned long, Q));
+ mpz_tdiv_r (Qk, T2, n);
+ }
+ }
+
+ return res;
+}
diff -r 395fb75310ab -r 94b7b61a3ff0 tests/mpz/Makefile.am
--- a/tests/mpz/Makefile.am Thu Nov 08 19:22:54 2018 +0100
+++ b/tests/mpz/Makefile.am Sat Nov 10 14:13:27 2018 +0100
@@ -26,7 +26,7 @@
t-fdiv_ui t-cdiv_ui t-gcd t-gcd_ui t-lcm t-invert dive dive_ui t-sqrtrem \
convert io t-inp_str logic bit t-powm t-powm_ui t-pow t-div_2exp \
t-root t-perfsqr t-perfpow t-jac t-bin t-get_d t-get_d_2exp t-get_si \
- t-set_d t-set_si \
+ t-set_d t-set_si t-lucm \
t-fac_ui t-mfac_uiui t-primorial_ui t-fib_ui t-lucnum_ui t-scan t-fits \
t-divis t-divis_2exp t-cong t-cong_2exp t-sizeinbase t-set_str \
t-aorsmul t-cmp_d t-cmp_si t-hamdist t-oddeven t-popcount t-set_f \
diff -r 395fb75310ab -r 94b7b61a3ff0 tests/mpz/t-lucm.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/mpz/t-lucm.c Sat Nov 10 14:13:27 2018 +0100
@@ -0,0 +1,144 @@
+/* Test mpz_powm, mpz_lucas_mod.
+
+Copyright 1991, 1993, 1994, 1996, 1999-2001, 2009, 2012, 2018 Free Software
+Foundation, Inc.
+
+This file is part of the GNU MP Library test suite.
+
+The GNU MP Library test suite is free software; you can redistribute it
+and/or modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 3 of the License,
+or (at your option) any later version.
+
+The GNU MP Library test suite is distributed in the hope that it will be
+useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
+Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "gmp-impl.h"
+#include "tests.h"
+
+void debug_mp (mpz_t, int);
+
+#define SIZEM 8
+
+/* FIXME: Should we implement another sequence to test lucas mod? */
+/* Eg: a generalisation of what we use for Fibonacci: */
+/* U_{2n-1} = U_n^2 - Q*U_{n-1}^2 */
+/* U_{2n+1} = D*U_n^2 + Q*U_{2n-1} + 2*Q^n ; whith D = (P^2-4*Q) */
+/* P*U_{2n} = U_{2n+1} + Q*U_{2n-1} */
+
+int
+main (int argc, char **argv)
+{
+ mpz_t base, exp, mod;
+ mpz_t r1, r2, t1, t2;
+ mp_size_t base_size, exp_size, mod_size;
+ int i, res;
+ int reps = 1000;
+ long Q;
+ gmp_randstate_ptr rands;
+ mpz_t bs;
+ unsigned long bsi, size_range;
+
+ tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
+ rands = RANDS;
+
+ mpz_init (bs);
+
+ mpz_init (base);
+ mpz_init (exp);
+ mpz_init (mod);
+ mpz_init (r1);
+ mpz_init (r2);
+ mpz_init (t1);
+ mpz_init (t2);
+
+ for (i = 0; i < reps; i++)
+ {
+ mpz_urandomb (bs, rands, 32);
+ size_range = mpz_get_ui (bs) % SIZEM + 1;
+
+ do /* Loop until base >= 2 and fits in a long. */
+ {
+ mpz_urandomb (base, rands, BITS_PER_ULONG - 2);
+ }
+ while (mpz_cmp_ui (base, 2) < 0 || mpz_fits_slong_p (base) == 0);
+
+ Q = mpz_get_ui (base);
+
+ do
+ {
+ ++size_range;
+ size_range = MIN (size_range, SIZEM);
+ mpz_urandomb (bs, rands, size_range);
+ mod_size = mpz_get_ui (bs);
+ mpz_rrandomb (mod, rands, mod_size);
+ mpz_add_ui (mod, mod, 16);
+ }
+ while (mpz_gcd_ui (NULL, mod, Q) != 1);
+
+ mod_size = mpz_sizeinbase (mod, 2) - 3;
+ mpz_urandomb (bs, rands, 32);
+ exp_size = mpz_get_ui (bs) % mod_size + 2;
+
+ mpz_tdiv_q_2exp (exp, mod, exp_size);
+ mpz_add_ui (exp, exp, 1);
+
+ mpz_urandomb (bs, rands, 2);
+ bsi = mpz_get_ui (bs);
+ if ((bsi & 1) != 0)
+ {
+ mpz_neg (base, base);
+ Q = -Q;
+ }
+
+ res = mpz_lucas_mod (t1, r2, Q, exp_size, mod, t2, r1);
+ if (res && ++reps)
+ continue;
+ MPZ_CHECK_FORMAT (r2);
+ if (mpz_cmp_ui (r2, 0) < 0)
+ mpz_add (r2, r2, mod);
+ mpz_powm (r1, base, exp, mod);
+
+ if (mpz_cmp (r1, r2) != 0)
+ {
+ fprintf (stderr, "\nIncorrect results in test %d for operands:\n", i);
+ debug_mp (base, -16);
More information about the gmp-commit
mailing list