Mercurial > dropbear

comparison bn_mp_is_square.c @ 1:22d5cf7d4b1a libtommath

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children d29b64170cf0
comparison
equal deleted inserted replaced
-1:000000000000 1:22d5cf7d4b1a
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */
15 #include <tommath.h>
16
17 /* Check if remainders are possible squares - fast exclude non-squares */
18 static const char rem_128[128] = {
19 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
20 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
21 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
22 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
23 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
24 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
25 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
26 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
27 };
28
29 static const char rem_105[105] = {
30 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
31 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
32 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
33 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
34 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
35 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
36 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
37 };
38
39 /* Store non-zero to ret if arg is square, and zero if not */
40 int mp_is_square(mp_int *arg,int *ret)
41 {
42 int res;
43 mp_digit c;
44 mp_int t;
45 unsigned long r;
46
47 /* Default to Non-square :) */
48 *ret = MP_NO;
49
50 if (arg->sign == MP_NEG) {
51 return MP_VAL;
52 }
53
54 /* digits used? (TSD) */
55 if (arg->used == 0) {
56 return MP_OKAY;
57 }
58
59 /* First check mod 128 (suppose that DIGIT_BIT is at least 7) */
60 if (rem_128[127 & DIGIT(arg,0)] == 1) {
61 return MP_OKAY;
62 }
63
64 /* Next check mod 105 (3*5*7) */
65 if ((res = mp_mod_d(arg,105,&c)) != MP_OKAY) {
66 return res;
67 }
68 if (rem_105[c] == 1) {
69 return MP_OKAY;
70 }
71
72 /* product of primes less than 2^31 */
73 if ((res = mp_init_set_int(&t,11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) {
74 return res;
75 }
76 if ((res = mp_mod(arg,&t,&t)) != MP_OKAY) {
77 goto ERR;
78 }
79 r = mp_get_int(&t);
80 /* Check for other prime modules, note it's not an ERROR but we must
81 * free "t" so the easiest way is to goto ERR. We know that res
82 * is already equal to MP_OKAY from the mp_mod call
83 */
84 if ( (1L<<(r%11)) & 0x5C4L ) goto ERR;
85 if ( (1L<<(r%13)) & 0x9E4L ) goto ERR;
86 if ( (1L<<(r%17)) & 0x5CE8L ) goto ERR;
87 if ( (1L<<(r%19)) & 0x4F50CL ) goto ERR;
88 if ( (1L<<(r%23)) & 0x7ACCA0L ) goto ERR;
89 if ( (1L<<(r%29)) & 0xC2EDD0CL ) goto ERR;
90 if ( (1L<<(r%31)) & 0x6DE2B848L ) goto ERR;
91
92 /* Final check - is sqr(sqrt(arg)) == arg ? */
93 if ((res = mp_sqrt(arg,&t)) != MP_OKAY) {
94 goto ERR;
95 }
96 if ((res = mp_sqr(&t,&t)) != MP_OKAY) {
97 goto ERR;
98 }
99
100 *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO;
101 ERR:mp_clear(&t);
102 return res;
103 }