summaryrefslogtreecommitdiffhomepage
path: root/libtommath/bn_mp_is_square.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtommath/bn_mp_is_square.c')
-rw-r--r--libtommath/bn_mp_is_square.c150
1 files changed, 74 insertions, 76 deletions
diff --git a/libtommath/bn_mp_is_square.c b/libtommath/bn_mp_is_square.c
index dd08d58..b1d2116 100644
--- a/libtommath/bn_mp_is_square.c
+++ b/libtommath/bn_mp_is_square.c
@@ -1,4 +1,4 @@
-#include <tommath_private.h>
+#include "tommath_private.h"
#ifdef BN_MP_IS_SQUARE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
*
@@ -9,101 +9,99 @@
* Michael Fromberger but has been written from scratch with
* additional optimizations in place.
*
- * The library is free for all purposes without any express
- * guarantee it works.
- *
- * Tom St Denis, tstdenis82@gmail.com, http://libtom.org
+ * SPDX-License-Identifier: Unlicense
*/
/* Check if remainders are possible squares - fast exclude non-squares */
static const char rem_128[128] = {
- 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
+ 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
};
static const char rem_105[105] = {
- 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
- 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
- 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
- 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
- 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
- 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
- 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
+ 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
+ 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
+ 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
+ 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
+ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
};
/* Store non-zero to ret if arg is square, and zero if not */
-int mp_is_square(mp_int *arg,int *ret)
+int mp_is_square(const mp_int *arg, int *ret)
{
- int res;
- mp_digit c;
- mp_int t;
- unsigned long r;
+ int res;
+ mp_digit c;
+ mp_int t;
+ unsigned long r;
- /* Default to Non-square :) */
- *ret = MP_NO;
+ /* Default to Non-square :) */
+ *ret = MP_NO;
- if (arg->sign == MP_NEG) {
- return MP_VAL;
- }
+ if (arg->sign == MP_NEG) {
+ return MP_VAL;
+ }
- /* digits used? (TSD) */
- if (arg->used == 0) {
- return MP_OKAY;
- }
+ /* digits used? (TSD) */
+ if (arg->used == 0) {
+ return MP_OKAY;
+ }
- /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */
- if (rem_128[127 & DIGIT(arg,0)] == 1) {
- return MP_OKAY;
- }
+ /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */
+ if (rem_128[127u & DIGIT(arg, 0)] == (char)1) {
+ return MP_OKAY;
+ }
- /* Next check mod 105 (3*5*7) */
- if ((res = mp_mod_d(arg,105,&c)) != MP_OKAY) {
- return res;
- }
- if (rem_105[c] == 1) {
- return MP_OKAY;
- }
+ /* Next check mod 105 (3*5*7) */
+ if ((res = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) {
+ return res;
+ }
+ if (rem_105[c] == (char)1) {
+ return MP_OKAY;
+ }
- if ((res = mp_init_set_int(&t,11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) {
- return res;
- }
- if ((res = mp_mod(arg,&t,&t)) != MP_OKAY) {
- goto ERR;
- }
- r = mp_get_int(&t);
- /* Check for other prime modules, note it's not an ERROR but we must
- * free "t" so the easiest way is to goto ERR. We know that res
- * is already equal to MP_OKAY from the mp_mod call
- */
- if (((1L<<(r%11)) & 0x5C4L) != 0L) goto ERR;
- if (((1L<<(r%13)) & 0x9E4L) != 0L) goto ERR;
- if (((1L<<(r%17)) & 0x5CE8L) != 0L) goto ERR;
- if (((1L<<(r%19)) & 0x4F50CL) != 0L) goto ERR;
- if (((1L<<(r%23)) & 0x7ACCA0L) != 0L) goto ERR;
- if (((1L<<(r%29)) & 0xC2EDD0CL) != 0L) goto ERR;
- if (((1L<<(r%31)) & 0x6DE2B848L) != 0L) goto ERR;
+ if ((res = mp_init_set_int(&t, 11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) {
+ return res;
+ }
+ if ((res = mp_mod(arg, &t, &t)) != MP_OKAY) {
+ goto LBL_ERR;
+ }
+ r = mp_get_int(&t);
+ /* Check for other prime modules, note it's not an ERROR but we must
+ * free "t" so the easiest way is to goto LBL_ERR. We know that res
+ * is already equal to MP_OKAY from the mp_mod call
+ */
+ if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%19uL)) & 0x4F50CuL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL) goto LBL_ERR;
+ if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL) goto LBL_ERR;
- /* Final check - is sqr(sqrt(arg)) == arg ? */
- if ((res = mp_sqrt(arg,&t)) != MP_OKAY) {
- goto ERR;
- }
- if ((res = mp_sqr(&t,&t)) != MP_OKAY) {
- goto ERR;
- }
+ /* Final check - is sqr(sqrt(arg)) == arg ? */
+ if ((res = mp_sqrt(arg, &t)) != MP_OKAY) {
+ goto LBL_ERR;
+ }
+ if ((res = mp_sqr(&t, &t)) != MP_OKAY) {
+ goto LBL_ERR;
+ }
- *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO;
-ERR:mp_clear(&t);
- return res;
+ *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO;
+LBL_ERR:
+ mp_clear(&t);
+ return res;
}
#endif
-/* ref: $Format:%D$ */
-/* git commit: $Format:%H$ */
-/* commit time: $Format:%ai$ */
+/* ref: HEAD -> master, tag: v1.1.0 */
+/* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
+/* commit time: 2019-01-28 20:32:32 +0100 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 11:18:31 +0000