Commit 03de03dee753442d4b23166982514639c4ccbc39
2022-10-28T15:49:30
Merge pull request #535 from czurnieden/bugfix_invmod Fix: removed sign operation in s_mp_invmod_odd (issue #534)
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
diff --git a/demo/test.c b/demo/test.c
index 16fef55..0ebcfd0 100644
--- a/demo/test.c
+++ b/demo/test.c
@@ -549,6 +549,54 @@ LBL_ERR:
static int test_mp_invmod(void)
{
mp_int a, b, c, d;
+ int i, j, k;
+ int e;
+
+ int results[21][21] =
+ /* Table generated with Pari/GP
+
+ for(i=-10,10,
+ k=0;
+ d=0;
+ printf(" {");
+ for(j=-10,10,
+ iferr(
+ printf(lift(Mod(1/i, j)) ", "),
+ k,
+ printf("-1, "))
+ );
+ print("},")
+ )
+
+ Changes to the output: replaced j < 1 with -1 for now and added the result of 0^(-1) mod (1)
+
+ j = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 */
+
+ {
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, -1, -1, -1, 2, -1, 8, -1 }, /* i = -10 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 3, 1, -1, 3, 7, -1, 1 }, /* -9 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 3, -1, 6, -1, 1, -1 }, /* -8 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 1, 2, 5, -1, 1, 5, 7 }, /* -7 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, 1, -1, -1, -1 }, /* -6 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, 3, -1, 1, 4, 3, 7, -1 }, /* -5 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, -1, 1, -1, 5, -1, 2, -1 }, /* -4 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 1, 3, -1, 2, 5, -1, 3 }, /* -3 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 2, -1, 3, -1, 4, -1 }, /* -2 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, /* -1 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1 }, /* 0 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, /* 1 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 2, -1, 3, -1, 4, -1, 5, -1 }, /* 2 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, 3, 2, -1, 5, 3, -1, 7 }, /* 3 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, -1, 4, -1, 2, -1, 7, -1 }, /* 4 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 1, -1, 5, 3, 5, 2, -1 }, /* 5 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, 1, -1, 6, -1, -1, -1 }, /* 6 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 3, 3, 1, -1, 7, 4, 3 }, /* 7 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 2, -1, 2, -1, 1, -1, 8, -1 }, /* 8 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, -1, 1, 4, -1, 4, 1, -1, 9 }, /* 9 */
+ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, -1, -1, -1, 5, -1, 1, -1 } /* 10 */
+ };
+
+
DOR(mp_init_multi(&a, &b, &c, &d, NULL));
/* mp_invmod corner-case of https://github.com/libtom/libtommath/issues/118 */
@@ -564,6 +612,30 @@ static int test_mp_invmod(void)
EXPECT(mp_cmp(&c, &d) == MP_EQ);
}
+ /* Some small general tests https://github.com/libtom/libtommath/issues/534 */
+ for (i = -10; i < 11; i++) {
+ for (j = -10; j < 11; j++) {
+ mp_set_i32(&a, i);
+ mp_set_i32(&b, j);
+ e = mp_invmod(&a, &b, &c);
+ if (e != MP_OKAY) {
+ if (results[i+10][j+10] != -1) {
+ printf("error = %s from ", mp_error_to_string(e));
+ printf("error at i = %d, j =%d should be an error but gave ",i,j);
+ e = mp_fwrite(&c,10,stdout);
+ printf("\n");
+ goto LBL_ERR;
+ }
+ } else {
+ k = mp_get_i32(&c);
+ if (k != results[i+10][j+10]) {
+ printf("result at i = %d, j =%d is %d but should be %d \n", i,j,k,results[i+10][j+10]);
+ goto LBL_ERR;
+ }
+ }
+ }
+ }
+
mp_clear_multi(&a, &b, &c, &d, NULL);
return EXIT_SUCCESS;
LBL_ERR:
diff --git a/s_mp_invmod.c b/s_mp_invmod.c
index f3b3f43..b2fb21d 100644
--- a/s_mp_invmod.c
+++ b/s_mp_invmod.c
@@ -98,7 +98,7 @@ mp_err s_mp_invmod(const mp_int *a, const mp_int *b, mp_int *c)
}
/* if its too low */
- while (mp_cmp_d(&C, 0uL) == MP_LT) {
+ while (mp_isneg(&C)) {
if ((err = mp_add(&C, b, &C)) != MP_OKAY) goto LBL_ERR;
}
diff --git a/s_mp_invmod_odd.c b/s_mp_invmod_odd.c
index e12dfa1..11fc357 100644
--- a/s_mp_invmod_odd.c
+++ b/s_mp_invmod_odd.c
@@ -12,7 +12,6 @@
mp_err s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c)
{
mp_int x, y, u, v, B, D;
- mp_sign sign;
mp_err err;
/* 2. [modified] b must be odd */
@@ -28,7 +27,7 @@ mp_err s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c)
/* x == modulus, y == value to invert */
if ((err = mp_copy(b, &x)) != MP_OKAY) goto LBL_ERR;
- /* we need y = |a| */
+ /* y needs to be positive but the remainder d of mp_div(a,b,c,d) might be negative */
if ((err = mp_mod(a, b, &y)) != MP_OKAY) goto LBL_ERR;
/* if one of x,y is zero return an error! */
@@ -95,7 +94,6 @@ mp_err s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c)
}
/* b is now the inverse */
- sign = a->sign;
while (mp_isneg(&D)) {
if ((err = mp_add(&D, b, &D)) != MP_OKAY) goto LBL_ERR;
}
@@ -106,7 +104,6 @@ mp_err s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c)
}
mp_exch(&D, c);
- c->sign = sign;
err = MP_OKAY;
LBL_ERR: