Commit e9c4590d4e8e829cd6019944f70cbbb5873f6784
2019-05-21T15:23:31
Merge pull request #280 from czurnieden/toom_cook_2_3_tests Tests for Karatsuba and Toom-Cook 3-way
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
diff --git a/demo/test.c b/demo/test.c
index 7b2abd2..a5ca63d 100644
--- a/demo/test.c
+++ b/demo/test.c
@@ -1883,6 +1883,137 @@ LTM_ERR:
return EXIT_FAILURE;
}
+#define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
+static int test_s_mp_karatsuba_mul(void)
+{
+ mp_int a, b, c, d;
+ int size, err;
+
+ if ((err = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ for (size = MP_KARATSUBA_MUL_CUTOFF; size < MP_KARATSUBA_MUL_CUTOFF + 20; size++) {
+ if ((err = mp_rand(&a, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = mp_rand(&b, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_karatsuba_mul(&a, &b, &c)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_mul(&a,&b,&d)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&c, &d) != MP_EQ) {
+ fprintf(stderr, "Karatsuba multiplication failed at size %d\n", size);
+ goto LTM_ERR;
+ }
+ }
+
+ mp_clear_multi(&a, &b, &c, &d, NULL);
+ return EXIT_SUCCESS;
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, &d, NULL);
+ return EXIT_FAILURE;
+}
+
+static int test_s_mp_karatsuba_sqr(void)
+{
+ mp_int a, b, c;
+ int size, err;
+
+ if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ for (size = MP_KARATSUBA_SQR_CUTOFF; size < MP_KARATSUBA_SQR_CUTOFF + 20; size++) {
+ if ((err = mp_rand(&a, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_karatsuba_sqr(&a, &b)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_sqr(&a, &c)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&b, &c) != MP_EQ) {
+ fprintf(stderr, "Karatsuba squaring failed at size %d\n", size);
+ goto LTM_ERR;
+ }
+ }
+
+ mp_clear_multi(&a, &b, &c, NULL);
+ return EXIT_SUCCESS;
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, NULL);
+ return EXIT_FAILURE;
+}
+
+static int test_s_mp_toom_mul(void)
+{
+ mp_int a, b, c, d;
+ int size, err;
+
+ if ((err = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ for (size = MP_TOOM_MUL_CUTOFF; size < MP_TOOM_MUL_CUTOFF + 20; size++) {
+ if ((err = mp_rand(&a, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = mp_rand(&b, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_toom_mul(&a, &b, &c)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_mul(&a,&b,&d)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&c, &d) != MP_EQ) {
+ fprintf(stderr, "Toom-Cook 3-way multiplication failed at size %d\n", size);
+ goto LTM_ERR;
+ }
+ }
+
+ mp_clear_multi(&a, &b, &c, &d, NULL);
+ return EXIT_SUCCESS;
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, &d, NULL);
+ return EXIT_FAILURE;
+}
+
+static int test_s_mp_toom_sqr(void)
+{
+ mp_int a, b, c;
+ int size, err;
+
+ if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ for (size = MP_TOOM_SQR_CUTOFF; size < MP_TOOM_SQR_CUTOFF + 20; size++) {
+ if ((err = mp_rand(&a, size)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_toom_sqr(&a, &b)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if ((err = s_mp_sqr(&a, &c)) != MP_OKAY) {
+ goto LTM_ERR;
+ }
+ if (mp_cmp(&b, &c) != MP_EQ) {
+ fprintf(stderr, "Toom-Cook 3-way squaring failed at size %d\n", size);
+ goto LTM_ERR;
+ }
+ }
+
+ mp_clear_multi(&a, &b, &c, NULL);
+ return EXIT_SUCCESS;
+LTM_ERR:
+ mp_clear_multi(&a, &b, &c, NULL);
+ return EXIT_FAILURE;
+}
+
int unit_tests(int argc, char **argv)
{
static const struct {
@@ -1921,7 +2052,11 @@ int unit_tests(int argc, char **argv)
T(mp_tc_or),
T(mp_tc_xor),
T(s_mp_balance_mul),
- T(s_mp_jacobi)
+ T(s_mp_jacobi),
+ T(s_mp_karatsuba_mul),
+ T(s_mp_karatsuba_sqr),
+ T(s_mp_toom_mul),
+ T(s_mp_toom_sqr)
#undef T
};
unsigned long i;