File size: 7,068 Bytes
78d2150 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 |
#include "../../unity/unity.h"
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <gmp.h>
/* Helpers specific to testing mulredc. We rely on internal
functions/macros from the factor implementation: binv_limb and redcify. */
/* Convert a single limb to an mpz_t using mpz_import, to avoid width issues. */
static void mpz_set_limb(mpz_t z, mp_limb_t x) {
mpz_import(z, 1, -1, sizeof(mp_limb_t), 0, 0, &x);
}
/* Compute R = B mod m using redcify macro: redcify(R, 1, m). */
static mp_limb_t mont_R_mod_m(mp_limb_t m) {
mp_limb_t R;
redcify(R, 1, m);
return R;
}
/* Compute xR = x * B mod m using redcify macro. Requires x < m and m odd. */
static mp_limb_t mont_redcify_value(mp_limb_t x, mp_limb_t m) {
mp_limb_t xR;
redcify(xR, x, m);
return xR;
}
/* Compute expected redc result for mulredc(aR, bR, m, mi), which should be
(a*b mod m) * R mod m, where a,b are the corresponding standard reps.
a and b must be < m. */
static mp_limb_t expected_redc_mul(mp_limb_t a, mp_limb_t b, mp_limb_t m) {
mpz_t A, B, M, T, Rz;
mpz_inits(A, B, M, T, Rz, NULL);
mpz_set_limb(A, a);
mpz_set_limb(B, b);
mpz_set_limb(M, m);
mpz_mul(T, A, B);
mpz_mod(T, T, M);
mp_limb_t R = mont_R_mod_m(m);
mpz_set_limb(Rz, R);
mpz_mul(T, T, Rz);
mpz_mod(T, T, M);
mp_limb_t out = mpz_getlimbn(T, 0);
mpz_clears(A, B, M, T, Rz, NULL);
return out;
}
/* Check one test case for given m, a, b. Requires m odd, a < m, b < m. */
static void check_case(mp_limb_t m, mp_limb_t a, mp_limb_t b) {
TEST_ASSERT_TRUE_MESSAGE((m & 1u) == 1u, "Modulus must be odd");
TEST_ASSERT_TRUE(a < m);
TEST_ASSERT_TRUE(b < m);
mp_limb_t mi = binv_limb(m); /* mi = m^{-1} mod B */
mp_limb_t aR = mont_redcify_value(a, m);
mp_limb_t bR = mont_redcify_value(b, m);
mp_limb_t got = mulredc(aR, bR, m, mi);
mp_limb_t exp = expected_redc_mul(a, b, m);
/* Range check */
TEST_ASSERT_TRUE(got < m);
/* Value check */
TEST_ASSERT_EQUAL_HEX64_MESSAGE((uint64_t)exp, (uint64_t)got, "mulredc result mismatch");
}
void setUp(void) {
/* Nothing to set up */
}
void tearDown(void) {
/* Nothing to tear down */
}
/* Test small odd moduli with fixed values, including composite moduli. */
static void test_mulredc_small_moduli_fixed(void) {
const mp_limb_t moduli[] = {3, 5, 7, 9, 11, 15, 21, 25, 27, 33, 35};
for (size_t i = 0; i < sizeof(moduli)/sizeof(moduli[0]); i++) {
mp_limb_t m = moduli[i];
/* Try various a,b pairs including edges */
mp_limb_t vals[] = {0, 1, (m > 2 ? 2 : 1), m - 2, m - 1};
size_t nvals = sizeof(vals)/sizeof(vals[0]);
for (size_t ia = 0; ia < nvals; ia++) {
for (size_t ib = 0; ib < nvals; ib++) {
mp_limb_t a = vals[ia] % m;
mp_limb_t b = vals[ib] % m;
check_case(m, a, b);
/* Commutativity */
mp_limb_t mi = binv_limb(m);
mp_limb_t aR = mont_redcify_value(a, m);
mp_limb_t bR = mont_redcify_value(b, m);
mp_limb_t r1 = mulredc(aR, bR, m, mi);
mp_limb_t r2 = mulredc(bR, aR, m, mi);
TEST_ASSERT_EQUAL_HEX64((uint64_t)r1, (uint64_t)r2);
}
}
}
}
/* Test identities: multiplication by 0 and by 1 (in Montgomery form). */
static void test_mulredc_identities(void) {
/* Choose an odd modulus not too small */
mp_limb_t m = 1000003u; /* Prime, odd, < 2^32 and < 2^64 */
mp_limb_t mi = binv_limb(m);
/* R = B mod m, and 1R = R, 0R = 0 */
mp_limb_t R = mont_R_mod_m(m);
/* Test 0 * x = 0 */
for (mp_limb_t x = 0; x < 20; x++) {
mp_limb_t xR = mont_redcify_value(x, m);
mp_limb_t zeroR = mont_redcify_value(0, m);
mp_limb_t got = mulredc(zeroR, xR, m, mi);
TEST_ASSERT_EQUAL_HEX64(0u, (uint64_t)got);
got = mulredc(xR, zeroR, m, mi);
TEST_ASSERT_EQUAL_HEX64(0u, (uint64_t)got);
}
/* Test 1 * x = x in redc form */
for (mp_limb_t x = 0; x < 20; x++) {
mp_limb_t xR = mont_redcify_value(x, m);
/* "1" in redc form is R. */
mp_limb_t got = mulredc(R, xR, m, mi);
TEST_ASSERT_EQUAL_HEX64((uint64_t)xR, (uint64_t)got);
got = mulredc(xR, R, m, mi);
TEST_ASSERT_EQUAL_HEX64((uint64_t)xR, (uint64_t)got);
}
}
/* Randomized tests under a fixed modulus. */
static void test_mulredc_random_values(void) {
mp_limb_t m = 4294967291u; /* large 32-bit prime, odd; OK on 64-bit too */
mp_limb_t mi = binv_limb(m);
/* Simple LCG for deterministic pseudo-randoms */
uint64_t seed = 0x123456789abcdef0ULL;
for (int i = 0; i < 200; i++) {
seed = seed * 6364136223846793005ULL + 1ULL;
mp_limb_t a = (mp_limb_t)(seed % m);
seed = seed * 6364136223846793005ULL + 1ULL;
mp_limb_t b = (mp_limb_t)(seed % m);
check_case(m, a, b);
/* Also directly check commutativity */
mp_limb_t aR = mont_redcify_value(a, m);
mp_limb_t bR = mont_redcify_value(b, m);
mp_limb_t r1 = mulredc(aR, bR, m, mi);
mp_limb_t r2 = mulredc(bR, aR, m, mi);
TEST_ASSERT_EQUAL_HEX64((uint64_t)r1, (uint64_t)r2);
}
}
/* Test a modulus near the maximum limb to exercise carries and subtraction. */
static void test_mulredc_large_modulus_edge(void) {
mp_limb_t m = MP_LIMB_MAX - 123; /* ensure odd */
if ((m & 1u) == 0) m -= 1;
/* Keep a,b just below m to exercise large products */
mp_limb_t a = m - 2;
mp_limb_t b = m - 3;
check_case(m, a, b);
/* A few more around the edge */
check_case(m, m - 1, m - 1);
check_case(m, m - 5, m - 7);
check_case(m, m / 2, (m / 2) - 1);
}
/* Test repeated squaring: (a^k) in redc form via repeated mulredc. */
static void test_mulredc_repeated_squaring(void) {
mp_limb_t m = 1000003u; /* prime */
mp_limb_t mi = binv_limb(m);
mp_limb_t a = 123456u % m;
mp_limb_t aR = mont_redcify_value(a, m);
mp_limb_t X = aR; /* redc(a^1) */
for (unsigned k = 2; k <= 16; k++) {
X = mulredc(X, aR, m, mi); /* redc(a^k) */
/* Compute expected redc(a^k) */
/* Using GMP: (a^k mod m) * R mod m */
mpz_t A, M, T, Rz; mpz_inits(A, M, T, Rz, NULL);
mpz_set_limb(A, a);
mpz_set_limb(M, m);
mpz_pow_ui(T, A, k);
mpz_mod(T, T, M);
mp_limb_t R = mont_R_mod_m(m);
mpz_set_limb(Rz, R);
mpz_mul(T, T, Rz);
mpz_mod(T, T, M);
mp_limb_t exp = mpz_getlimbn(T, 0);
mpz_clears(A, M, T, Rz, NULL);
TEST_ASSERT_TRUE(X < m);
TEST_ASSERT_EQUAL_HEX64((uint64_t)exp, (uint64_t)X);
}
}
int main(void) {
UNITY_BEGIN();
RUN_TEST(test_mulredc_small_moduli_fixed);
RUN_TEST(test_mulredc_identities);
RUN_TEST(test_mulredc_random_values);
RUN_TEST(test_mulredc_large_modulus_edge);
RUN_TEST(test_mulredc_repeated_squaring);
return UNITY_END();
} |