[Gmp-commit] /home/hgfiles/gmp: Rewrote refmpz_legendre, and support it in try.c
mercurial at gmplib.org
mercurial at gmplib.org
Thu Feb 25 17:32:55 CET 2010
details: /home/hgfiles/gmp/rev/54fd94c86a89
changeset: 13441:54fd94c86a89
user: Niels M?ller <nisse at lysator.liu.se>
date: Thu Feb 25 17:23:46 2010 +0100
description:
Rewrote refmpz_legendre, and support it in try.c
diffstat:
ChangeLog | 10 +++++++++
tests/devel/try.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
tests/refmpz.c | 34 +++++++++++++++++++++++++++++-
3 files changed, 98 insertions(+), 5 deletions(-)
diffs (168 lines):
diff -r d66997641b54 -r 54fd94c86a89 ChangeLog
--- a/ChangeLog Thu Feb 25 16:08:31 2010 +0100
+++ b/ChangeLog Thu Feb 25 17:23:46 2010 +0100
@@ -1,3 +1,13 @@
+2010-02-25 Niels Möller <nisse at lysator.liu.se>
+
+ * tests/devel/try.c (param_init): Support mpz_legendre.
+ (choice_array): Added mpz_kronecker (apparently forgotten) and
+ mpz_legendre.
+ (call): Added TYPE_MPZ_LEGENDRE.
+ (try_one): Added support for DATA_SRC1_ODD_PRIME.
+
+ * tests/refmpz.c (refmpz_legendre): Rewrote using powm.
+
2010-02-25 Torbjorn Granlund <tege at gmplib.org>
* tests/mpn/t-div.c: Cast a switch index to placate HP's cc.
diff -r d66997641b54 -r 54fd94c86a89 tests/devel/try.c
--- a/tests/devel/try.c Thu Feb 25 16:08:31 2010 +0100
+++ b/tests/devel/try.c Thu Feb 25 17:23:46 2010 +0100
@@ -354,9 +354,10 @@
#define DATA_SRC0_ODD 3
#define DATA_SRC0_HIGHBIT 4
#define DATA_SRC1_ODD 5
-#define DATA_SRC1_HIGHBIT 6
-#define DATA_MULTIPLE_DIVISOR 7
-#define DATA_UDIV_QRNND 8
+#define DATA_SRC1_ODD_PRIME 6
+#define DATA_SRC1_HIGHBIT 7
+#define DATA_MULTIPLE_DIVISOR 8
+#define DATA_UDIV_QRNND 9
char data;
/* Default is allow full overlap. */
@@ -633,6 +634,7 @@
#define TYPE_MPZ_KRONECKER_SI 66
#define TYPE_MPZ_UI_KRONECKER 67
#define TYPE_MPZ_SI_KRONECKER 68
+#define TYPE_MPZ_LEGENDRE 69
#define TYPE_AND_N 70
#define TYPE_NAND_N 71
@@ -1052,6 +1054,17 @@
REFERENCE (refmpn_gcd);
+ p = ¶m[TYPE_MPZ_LEGENDRE];
+ p->retval = 1;
+ p->src[0] = 1;
+ p->size = SIZE_ALLOW_ZERO;
+ p->src[1] = 1;
+ p->data = DATA_SRC1_ODD_PRIME;
+ p->size2 = 1;
+ p->carry = CARRY_BIT;
+ p->carry_sign = 1;
+ REFERENCE (refmpz_legendre);
+
p = ¶m[TYPE_MPZ_JACOBI];
p->retval = 1;
p->src[0] = 1;
@@ -1588,7 +1601,9 @@
{ TRY(mpn_gcd_1), TYPE_GCD_1 },
{ TRY(mpn_gcd), TYPE_GCD },
+ { TRY(mpz_legendre), TYPE_MPZ_LEGENDRE },
{ TRY(mpz_jacobi), TYPE_MPZ_JACOBI },
+ { TRY(mpz_kronecker), TYPE_MPZ_KRONECKER },
{ TRY(mpz_kronecker_ui), TYPE_MPZ_KRONECKER_UI },
{ TRY(mpz_kronecker_si), TYPE_MPZ_KRONECKER_SI },
{ TRY(mpz_ui_kronecker), TYPE_MPZ_UI_KRONECKER },
@@ -2259,6 +2274,14 @@
}
break;
+ case TYPE_MPZ_LEGENDRE:
+ {
+ mpz_t a, b;
+ PTR(a) = e->s[0].p; SIZ(a) = (carry==0 ? size : -size);
+ PTR(b) = e->s[1].p; SIZ(b) = size2;
+ e->retval = CALLING_CONVENTIONS (function) (a, b);
+ }
+ break;
case TYPE_MPZ_JACOBI:
case TYPE_MPZ_KRONECKER:
{
@@ -2634,6 +2657,36 @@
s[i].p[0] |= 1;
break;
+ case DATA_SRC1_ODD_PRIME:
+ if (i == 1)
+ {
+ if (refmpn_zero_p (s[i].p+1, SRC_SIZE(i)-1)
+ && s[i].p[0] <=3)
+ s[i].p[0] = 3;
+ else
+ {
+ mpz_t p;
+ mpz_init (p);
+ for (;;)
+ {
+ _mpz_realloc (p, SRC_SIZE(i));
+ MPN_COPY (PTR(p), s[i].p, SRC_SIZE(i));
+ SIZ(p) = SRC_SIZE(i);
+ MPN_NORMALIZE (PTR(p), SIZ(p));
+ mpz_nextprime (p, p);
+ if (mpz_size (p) <= SRC_SIZE(i))
+ break;
+
+ t_random (s[i].p, SRC_SIZE(i));
+ }
+ MPN_COPY (s[i].p, PTR(p), SIZ(p));
+ if (SIZ(p) < SRC_SIZE(i))
+ MPN_ZERO (s[i].p + SIZ(p), SRC_SIZE(i) - SIZ(p));
+ mpz_clear (p);
+ }
+ }
+ break;
+
case DATA_SRC1_HIGHBIT:
if (i == 1)
{
diff -r d66997641b54 -r 54fd94c86a89 tests/refmpz.c
--- a/tests/refmpz.c Thu Feb 25 16:08:31 2010 +0100
+++ b/tests/refmpz.c Thu Feb 25 17:23:46 2010 +0100
@@ -191,10 +191,40 @@
return refmpz_kronecker (a, b_odd);
}
+/* Legendre symbol via powm. p must be an odd prime. */
int
-refmpz_legendre (mpz_srcptr a, mpz_srcptr b)
+refmpz_legendre (mpz_srcptr a, mpz_srcptr p)
{
- return refmpz_jacobi (a, b);
+ int res;
+
+ mpz_t r;
+ mpz_t e;
+
+ ASSERT_ALWAYS (mpz_sgn (p) > 0);
+ ASSERT_ALWAYS (mpz_odd_p (p));
+
+ mpz_init (r);
+ mpz_init (e);
+
+ mpz_fdiv_r (r, a, p);
+
+ mpz_set (e, p);
+ mpz_sub_ui (e, e, 1);
+ mpz_fdiv_q_2exp (e, e, 1);
+ mpz_powm (r, r, e, p);
+
+ /* Normalize to a more or less symmetric range around zero */
+ if (mpz_cmp (r, e) > 0)
+ mpz_sub (r, r, p);
+
+ ASSERT_ALWAYS (mpz_cmpabs_ui (r, 1) <= 0);
+
+ res = mpz_sgn (r);
+
+ mpz_clear (r);
+ mpz_clear (e);
+
+ return res;
}
More information about the gmp-commit
mailing list