]>
Commit | Line | Data |
---|---|---|
f064ef39 NM |
1 | /* ecc-pm1-redc.c |
2 | ||
3 | Copyright (C) 2013, 2014 Niels Möller | |
4 | ||
5 | This file is part of GNU Nettle. | |
6 | ||
7 | GNU Nettle is free software: you can redistribute it and/or | |
8 | modify it under the terms of either: | |
9 | ||
10 | * the GNU Lesser General Public License as published by the Free | |
11 | Software Foundation; either version 3 of the License, or (at your | |
12 | option) any later version. | |
13 | ||
14 | or | |
15 | ||
16 | * the GNU General Public License as published by the Free | |
17 | Software Foundation; either version 2 of the License, or (at your | |
18 | option) any later version. | |
19 | ||
20 | or both in parallel, as here. | |
21 | ||
22 | GNU Nettle is distributed in the hope that it will be useful, | |
23 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
24 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
25 | General Public License for more details. | |
26 | ||
27 | You should have received copies of the GNU General Public License and | |
28 | the GNU Lesser General Public License along with this program. If | |
29 | not, see http://www.gnu.org/licenses/. | |
30 | */ | |
31 | ||
32 | /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ | |
33 | ||
34 | #if HAVE_CONFIG_H | |
35 | # include "config.h" | |
36 | #endif | |
37 | ||
38 | #include <assert.h> | |
39 | ||
40 | #include "ecc-internal.h" | |
41 | ||
42 | /* Use that 1 = - (p - 1) (mod p), and that at least one low limb of p | |
43 | - 1 is zero. */ | |
44 | void | |
f4f5625e | 45 | ecc_pm1_redc (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp) |
f064ef39 NM |
46 | { |
47 | unsigned i; | |
48 | mp_limb_t hi, cy; | |
0b511c91 NM |
49 | unsigned shift = m->size * GMP_NUMB_BITS - m->bit_size; |
50 | mp_size_t k = m->redc_size; | |
f064ef39 | 51 | |
0b511c91 | 52 | for (i = 0; i < m->size; i++) |
f4f5625e NM |
53 | xp[i] = mpn_submul_1 (xp + i + k, |
54 | m->redc_mpm1, m->size - k, xp[i]); | |
55 | hi = mpn_sub_n (xp, xp + m->size, xp, m->size); | |
56 | cy = mpn_cnd_add_n (hi, rp, xp, m->m, m->size); | |
cf8a68ef | 57 | assert_maybe (cy == hi); |
f064ef39 NM |
58 | |
59 | if (shift > 0) | |
60 | { | |
61 | /* Result is always < 2p, provided that | |
62 | 2^shift * Bmodp_shifted <= p */ | |
0b511c91 NM |
63 | hi = (rp[m->size - 1] >> (GMP_NUMB_BITS - shift)); |
64 | rp[m->size - 1] = (rp[m->size - 1] | |
f064ef39 | 65 | & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1)) |
0b511c91 | 66 | + mpn_addmul_1 (rp, m->B_shifted, m->size-1, hi); |
f064ef39 NM |
67 | } |
68 | } |