/src/dropbear/libtommath/bn_mp_is_square.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_IS_SQUARE_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* Check if remainders are possible squares - fast exclude non-squares */ |
7 | | static const char rem_128[128] = { |
8 | | 0, 0, 1, 1, 0, 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, |
10 | | 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, |
11 | | 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, |
12 | | 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, |
13 | | 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, |
14 | | 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, |
15 | | 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 |
16 | | }; |
17 | | |
18 | | static const char rem_105[105] = { |
19 | | 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, |
20 | | 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, |
21 | | 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, |
22 | | 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, |
23 | | 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, |
24 | | 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, |
25 | | 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1 |
26 | | }; |
27 | | |
28 | | /* Store non-zero to ret if arg is square, and zero if not */ |
29 | | mp_err mp_is_square(const mp_int *arg, mp_bool *ret) |
30 | 139 | { |
31 | 139 | mp_err err; |
32 | 139 | mp_digit c; |
33 | 139 | mp_int t; |
34 | 139 | unsigned long r; |
35 | | |
36 | | /* Default to Non-square :) */ |
37 | 139 | *ret = MP_NO; |
38 | | |
39 | 139 | if (arg->sign == MP_NEG) { |
40 | 0 | return MP_VAL; |
41 | 0 | } |
42 | | |
43 | 139 | if (MP_IS_ZERO(arg)) { |
44 | 0 | return MP_OKAY; |
45 | 0 | } |
46 | | |
47 | | /* First check mod 128 (suppose that MP_DIGIT_BIT is at least 7) */ |
48 | 139 | if (rem_128[127u & arg->dp[0]] == (char)1) { |
49 | 20 | return MP_OKAY; |
50 | 20 | } |
51 | | |
52 | | /* Next check mod 105 (3*5*7) */ |
53 | 119 | if ((err = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) { |
54 | 0 | return err; |
55 | 0 | } |
56 | 119 | if (rem_105[c] == (char)1) { |
57 | 87 | return MP_OKAY; |
58 | 87 | } |
59 | | |
60 | | |
61 | 32 | if ((err = mp_init_u32(&t, 11u*13u*17u*19u*23u*29u*31u)) != MP_OKAY) { |
62 | 0 | return err; |
63 | 0 | } |
64 | 32 | if ((err = mp_mod(arg, &t, &t)) != MP_OKAY) { |
65 | 0 | goto LBL_ERR; |
66 | 0 | } |
67 | 32 | r = mp_get_u32(&t); |
68 | | /* Check for other prime modules, note it's not an ERROR but we must |
69 | | * free "t" so the easiest way is to goto LBL_ERR. We know that err |
70 | | * is already equal to MP_OKAY from the mp_mod call |
71 | | */ |
72 | 32 | if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL) goto LBL_ERR; |
73 | 24 | if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL) goto LBL_ERR; |
74 | 19 | if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL) goto LBL_ERR; |
75 | 15 | if (((1uL<<(r%19uL)) & 0x4F50CuL) != 0uL) goto LBL_ERR; |
76 | 8 | if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL) goto LBL_ERR; |
77 | 7 | if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL) goto LBL_ERR; |
78 | 6 | if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL) goto LBL_ERR; |
79 | | |
80 | | /* Final check - is sqr(sqrt(arg)) == arg ? */ |
81 | 4 | if ((err = mp_sqrt(arg, &t)) != MP_OKAY) { |
82 | 0 | goto LBL_ERR; |
83 | 0 | } |
84 | 4 | if ((err = mp_sqr(&t, &t)) != MP_OKAY) { |
85 | 0 | goto LBL_ERR; |
86 | 0 | } |
87 | | |
88 | 4 | *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO; |
89 | 32 | LBL_ERR: |
90 | 32 | mp_clear(&t); |
91 | 32 | return err; |
92 | 4 | } |
93 | | #endif |