blob: 75feff8bc5e35bce6feaa8c6eb84a04195773d99 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <stdint.h>
#include "params.h"
#include "reduce.h"
/*************************************************
* Name: montgomery_reduce
*
* Description: For finite field element a with -2^{31}Q <= a <= Q*2^31,
* compute r \equiv a*2^{-32} (mod Q) such that -Q < r < Q.
*
* Arguments: - int64_t: finite field element a
*
* Returns r.
**************************************************/
int32_t montgomery_reduce(int64_t a) {
int32_t t;
t = (int64_t)(int32_t)a*QINV;
t = (a - (int64_t)t*Q) >> 32;
return t;
}
/*************************************************
* Name: reduce32
*
* Description: For finite field element a with a <= 2^{31} - 2^{22} - 1,
* compute r \equiv a (mod Q) such that -6283009 <= r <= 6283007.
*
* Arguments: - int32_t: finite field element a
*
* Returns r.
**************************************************/
int32_t reduce32(int32_t a) {
int32_t t;
t = (a + (1 << 22)) >> 23;
t = a - t*Q;
return t;
}
/*************************************************
* Name: caddq
*
* Description: Add Q if input coefficient is negative.
*
* Arguments: - int32_t: finite field element a
*
* Returns r.
**************************************************/
int32_t caddq(int32_t a) {
a += (a >> 31) & Q;
return a;
}
/*************************************************
* Name: freeze
*
* Description: For finite field element a, compute standard
* representative r = a mod^+ Q.
*
* Arguments: - int32_t: finite field element a
*
* Returns r.
**************************************************/
int32_t freeze(int32_t a) {
a = reduce32(a);
a = caddq(a);
return a;
}
|
