Mercurial > dropbear

comparison libtommath/bn_mp_is_square.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_IS_SQUARE_C 2 #ifdef BN_MP_IS_SQUARE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* Check if remainders are possible squares - fast exclude non-squares */ 6 /* Check if remainders are possible squares - fast exclude non-squares */
16 static const char rem_128[128] = { 7 static const char rem_128[128] = {
17 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 8 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
18 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 9 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
33 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 24 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
34 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 25 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
35 }; 26 };
36 27
37 /* Store non-zero to ret if arg is square, and zero if not */ 28 /* Store non-zero to ret if arg is square, and zero if not */
38 int mp_is_square(const mp_int *arg, int *ret) 29 mp_err mp_is_square(const mp_int *arg, mp_bool *ret)
39 { 30 {
40 int res; 31 mp_err err;
41 mp_digit c; 32 mp_digit c;
42 mp_int t; 33 mp_int t;
43 unsigned long r; 34 unsigned long r;
44 35
45 /* Default to Non-square :) */ 36 /* Default to Non-square :) */
47 38
48 if (arg->sign == MP_NEG) { 39 if (arg->sign == MP_NEG) {
49 return MP_VAL; 40 return MP_VAL;
50 } 41 }
51 42
52 /* digits used? (TSD) */ 43 if (MP_IS_ZERO(arg)) {
53 if (arg->used == 0) {
54 return MP_OKAY; 44 return MP_OKAY;
55 } 45 }
56 46
57 /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */ 47 /* First check mod 128 (suppose that MP_DIGIT_BIT is at least 7) */
58 if (rem_128[127u & DIGIT(arg, 0)] == (char)1) { 48 if (rem_128[127u & arg->dp[0]] == (char)1) {
59 return MP_OKAY; 49 return MP_OKAY;
60 } 50 }
61 51
62 /* Next check mod 105 (3*5*7) */ 52 /* Next check mod 105 (3*5*7) */
63 if ((res = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) { 53 if ((err = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) {
64 return res; 54 return err;
65 } 55 }
66 if (rem_105[c] == (char)1) { 56 if (rem_105[c] == (char)1) {
67 return MP_OKAY; 57 return MP_OKAY;
68 } 58 }
69 59
70 60
71 if ((res = mp_init_set_int(&t, 11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) { 61 if ((err = mp_init_u32(&t, 11u*13u*17u*19u*23u*29u*31u)) != MP_OKAY) {
72 return res; 62 return err;
73 } 63 }
74 if ((res = mp_mod(arg, &t, &t)) != MP_OKAY) { 64 if ((err = mp_mod(arg, &t, &t)) != MP_OKAY) {
75 goto LBL_ERR; 65 goto LBL_ERR;
76 } 66 }
77 r = mp_get_int(&t); 67 r = mp_get_u32(&t);
78 /* Check for other prime modules, note it's not an ERROR but we must 68 /* Check for other prime modules, note it's not an ERROR but we must
79 * free "t" so the easiest way is to goto LBL_ERR. We know that res 69 * free "t" so the easiest way is to goto LBL_ERR. We know that err
80 * is already equal to MP_OKAY from the mp_mod call 70 * is already equal to MP_OKAY from the mp_mod call
81 */ 71 */
82 if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL) goto LBL_ERR; 72 if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL) goto LBL_ERR;
83 if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL) goto LBL_ERR; 73 if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL) goto LBL_ERR;
84 if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL) goto LBL_ERR; 74 if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL) goto LBL_ERR;
86 if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL) goto LBL_ERR; 76 if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL) goto LBL_ERR;
87 if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL) goto LBL_ERR; 77 if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL) goto LBL_ERR;
88 if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL) goto LBL_ERR; 78 if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL) goto LBL_ERR;
89 79
90 /* Final check - is sqr(sqrt(arg)) == arg ? */ 80 /* Final check - is sqr(sqrt(arg)) == arg ? */
91 if ((res = mp_sqrt(arg, &t)) != MP_OKAY) { 81 if ((err = mp_sqrt(arg, &t)) != MP_OKAY) {
92 goto LBL_ERR; 82 goto LBL_ERR;
93 } 83 }
94 if ((res = mp_sqr(&t, &t)) != MP_OKAY) { 84 if ((err = mp_sqr(&t, &t)) != MP_OKAY) {
95 goto LBL_ERR; 85 goto LBL_ERR;
96 } 86 }
97 87
98 *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO; 88 *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO;
99 LBL_ERR: 89 LBL_ERR:
100 mp_clear(&t); 90 mp_clear(&t);
101 return res; 91 return err;
102 } 92 }
103 #endif 93 #endif
104
105 /* ref: HEAD -> master, tag: v1.1.0 */
106 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
107 /* commit time: 2019-01-28 20:32:32 +0100 */