Debian Codegraph @

external/boringssl/crypto/newhope/reduce.c

raw
1 /* Copyright (c) 2016, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 #include "internal.h"
16
17
18 /* Incomplete-reduction routines; for details on allowed input ranges
19 * and produced output ranges, see the description in the paper:
20 * https://cryptojedi.org/papers/#newhope */
21
22 static const uint32_t kQInv = 12287; /* -inverse_mod(p,2^18) */
23 static const uint32_t kRLog = 18;
24
25 uint16_t newhope_montgomery_reduce(uint32_t a) {
26 uint32_t u;
27
28 u = (a * kQInv);
29 u &= ((1 << kRLog) - 1);
30 u *= PARAM_Q;
31 a = a + u;
32 return a >> 18;
33 }
34
35 uint16_t newhope_barrett_reduce(uint16_t a) {
36 uint32_t u;
37
38 u = ((uint32_t)a * 5) >> 16;
39 u *= PARAM_Q;
40 a -= u;
41 return a;
42 }