|
Packit |
5c3484 |
/* Test for sqrmod_bnm1 function.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Contributed to the GNU project by Marco Bodrato.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2009 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library test suite.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is free software; you can redistribute it
|
|
Packit |
5c3484 |
and/or modify it under the terms of the GNU General Public License as
|
|
Packit |
5c3484 |
published by the Free Software Foundation; either version 3 of the License,
|
|
Packit |
5c3484 |
or (at your option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library test suite is distributed in the hope that it will be
|
|
Packit |
5c3484 |
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
5c3484 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
|
|
Packit |
5c3484 |
Public License for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received a copy of the GNU General Public License along with
|
|
Packit |
5c3484 |
the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include <stdlib.h>
|
|
Packit |
5c3484 |
#include <stdio.h>
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "tests.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Sizes are up to 2^SIZE_LOG limbs */
|
|
Packit |
5c3484 |
#ifndef SIZE_LOG
|
|
Packit |
5c3484 |
#define SIZE_LOG 12
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#ifndef COUNT
|
|
Packit |
5c3484 |
#define COUNT 3000
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define MAX_N (1L << SIZE_LOG)
|
|
Packit |
5c3484 |
#define MIN_N 1
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/*
|
|
Packit |
5c3484 |
Reference function for squaring modulo B^rn-1.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The result is expected to be ZERO if and only if one of the operand
|
|
Packit |
5c3484 |
already is. Otherwise the class [0] Mod(B^rn-1) is represented by
|
|
Packit |
5c3484 |
B^rn-1. This should not be a problem if sqrmod_bnm1 is used to
|
|
Packit |
5c3484 |
combine results and obtain a natural number when one knows in
|
|
Packit |
5c3484 |
advance that the final value is less than (B^rn-1).
|
|
Packit |
5c3484 |
*/
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
static void
|
|
Packit |
5c3484 |
ref_sqrmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_limb_t cy;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (0 < an && an <= rn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
refmpn_mul (rp, ap, an, ap, an);
|
|
Packit |
5c3484 |
an *= 2;
|
|
Packit |
5c3484 |
if (an > rn) {
|
|
Packit |
5c3484 |
cy = mpn_add (rp, rp, rn, rp + rn, an - rn);
|
|
Packit |
5c3484 |
/* If cy == 1, then the value of rp is at most B^rn - 2, so there can
|
|
Packit |
5c3484 |
* be no overflow when adding in the carry. */
|
|
Packit |
5c3484 |
MPN_INCR_U (rp, rn, cy);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/*
|
|
Packit |
5c3484 |
Compare the result of the mpn_sqrmod_bnm1 function in the library
|
|
Packit |
5c3484 |
with the reference function above.
|
|
Packit |
5c3484 |
*/
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
int
|
|
Packit |
5c3484 |
main (int argc, char **argv)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_ptr ap, refp, pp, scratch;
|
|
Packit |
5c3484 |
int count = COUNT;
|
|
Packit |
5c3484 |
int test;
|
|
Packit |
5c3484 |
gmp_randstate_ptr rands;
|
|
Packit |
5c3484 |
TMP_DECL;
|
|
Packit |
5c3484 |
TMP_MARK;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (argc > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
char *end;
|
|
Packit |
5c3484 |
count = strtol (argv[1], &end, 0);
|
|
Packit |
5c3484 |
if (*end || count <= 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
fprintf (stderr, "Invalid test count: %s.\n", argv[1]);
|
|
Packit |
5c3484 |
return 1;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
tests_start ();
|
|
Packit |
5c3484 |
rands = RANDS;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT_ALWAYS (mpn_sqrmod_bnm1_next_size (MAX_N) == MAX_N);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ap = TMP_ALLOC_LIMBS (MAX_N);
|
|
Packit |
5c3484 |
refp = TMP_ALLOC_LIMBS (MAX_N * 4);
|
|
Packit |
5c3484 |
pp = 1+TMP_ALLOC_LIMBS (MAX_N + 2);
|
|
Packit |
5c3484 |
scratch
|
|
Packit |
5c3484 |
= 1+TMP_ALLOC_LIMBS (mpn_sqrmod_bnm1_itch (MAX_N, MAX_N) + 2);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (test = 0; test < count; test++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
unsigned size_min;
|
|
Packit |
5c3484 |
unsigned size_range;
|
|
Packit |
5c3484 |
mp_size_t an,rn,n;
|
|
Packit |
5c3484 |
mp_size_t itch;
|
|
Packit |
5c3484 |
mp_limb_t p_before, p_after, s_before, s_after;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (size_min = 1; (1L << size_min) < MIN_N; size_min++)
|
|
Packit |
5c3484 |
;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* We generate an in the MIN_N <= n <= (1 << size_range). */
|
|
Packit |
5c3484 |
size_range = size_min
|
|
Packit |
5c3484 |
+ gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
n = MIN_N
|
|
Packit |
5c3484 |
+ gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N);
|
|
Packit |
5c3484 |
n = mpn_sqrmod_bnm1_next_size (n);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (n == 1)
|
|
Packit |
5c3484 |
an = 1;
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
an = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_random2 (ap, an);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Sometime trigger the borderline conditions
|
|
Packit |
5c3484 |
A = -1,0,+1 Mod(B^{n/2}+1).
|
|
Packit |
5c3484 |
This only makes sense if there is at least a split, i.e. n is even. */
|
|
Packit |
5c3484 |
if ((test & 0x1f) == 1 && (n & 1) == 0) {
|
|
Packit |
5c3484 |
mp_size_t x;
|
|
Packit |
5c3484 |
MPN_COPY (ap, ap + (n >> 1), an - (n >> 1));
|
|
Packit |
5c3484 |
MPN_ZERO (ap + an - (n >> 1) , n - an);
|
|
Packit |
5c3484 |
x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an);
|
|
Packit |
5c3484 |
ap[x] += gmp_urandomm_ui (rands, 3) - 1;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
rn = MIN(n, 2*an);
|
|
Packit |
5c3484 |
mpn_random2 (pp-1, rn + 2);
|
|
Packit |
5c3484 |
p_before = pp[-1];
|
|
Packit |
5c3484 |
p_after = pp[rn];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
itch = mpn_sqrmod_bnm1_itch (n, an);
|
|
Packit |
5c3484 |
ASSERT_ALWAYS (itch <= mpn_sqrmod_bnm1_itch (MAX_N, MAX_N));
|
|
Packit |
5c3484 |
mpn_random2 (scratch-1, itch+2);
|
|
Packit |
5c3484 |
s_before = scratch[-1];
|
|
Packit |
5c3484 |
s_after = scratch[itch];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_sqrmod_bnm1 ( pp, n, ap, an, scratch);
|
|
Packit |
5c3484 |
ref_sqrmod_bnm1 (refp, n, ap, an);
|
|
Packit |
5c3484 |
if (pp[-1] != p_before || pp[rn] != p_after
|
|
Packit |
5c3484 |
|| scratch[-1] != s_before || scratch[itch] != s_after
|
|
Packit |
5c3484 |
|| mpn_cmp (refp, pp, rn) != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("ERROR in test %d, an = %d, n = %d\n",
|
|
Packit |
5c3484 |
test, (int) an, (int) n);
|
|
Packit |
5c3484 |
if (pp[-1] != p_before)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("before pp:"); mpn_dump (pp -1, 1);
|
|
Packit |
5c3484 |
printf ("keep: "); mpn_dump (&p_before, 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
if (pp[rn] != p_after)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("after pp:"); mpn_dump (pp + rn, 1);
|
|
Packit |
5c3484 |
printf ("keep: "); mpn_dump (&p_after, 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
if (scratch[-1] != s_before)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("before scratch:"); mpn_dump (scratch-1, 1);
|
|
Packit |
5c3484 |
printf ("keep: "); mpn_dump (&s_before, 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
if (scratch[itch] != s_after)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf ("after scratch:"); mpn_dump (scratch + itch, 1);
|
|
Packit |
5c3484 |
printf ("keep: "); mpn_dump (&s_after, 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
mpn_dump (ap, an);
|
|
Packit |
5c3484 |
mpn_dump (pp, rn);
|
|
Packit |
5c3484 |
mpn_dump (refp, rn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
abort();
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
tests_end ();
|
|
Packit |
5c3484 |
return 0;
|
|
Packit |
5c3484 |
}
|