-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhelpers_int.h
103 lines (83 loc) · 3.54 KB
/
helpers_int.h
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* helpers_int.h -- helper functions for the long long version of tests
*
* Copyright 2014 by Colin Benner <[email protected]>
*
* This file is part of frobenius-test.
*
* frobenius-test is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* frobenius-test is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with frobenius-test. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef HELPERS_INT_H
#define HELPERS_INT_H
#include <stdbool.h>
#include <stdio.h>
#include "common.h"
/*
* The following lines are needed to use GMP's longlong.h which provides a
* macro for multiplying two 64-bit numbers to produce a 128-bit result which
* is stored across two registers.
*/
//#define W_TYPE_SIZE 64
//typedef uint64_t UWtype;
//typedef uint64_t UDItype;
//// Including the following file from GMP in the distribution forces this
//// programme to be licenced under the terms of the GPL.
//#include "longlong.h"
/* Multiply two numbers modulo n. */
#define mul(x, y) mul_mod_n(x, y, n)
uint64_t mul_mod_n(uint64_t x, uint64_t y, uint64_t n);
/*
* A few macros for passing commonly used arguments and declaring the
* corresponding parameters.
*/
#define POLY_int(f) f##_x, f##_1
#define POLY_ARGS_int(f) uint64_t *f##_x, uint64_t *f##_1
#define CONST_POLY_ARGS_int(f) const uint64_t f##_x, const uint64_t f##_1
#define MODULUS_int n, b, c
#define MODULUS_ARGS_int const uint64_t n, const uint64_t b, const uint64_t c
// Some macros to simplify handling polyonmial arithmetic.
#define poly_mul_int(res, f, g) mult_mod_int(res##_x, res##_1, f##_x, f##_1, g##_x, g##_1, MODULUS)
#define poly_sqr_int(res, f) square_mod_int(res##_x, res##_1, f##_x, f##_1, MODULUS)
#define poly_powm_int(res, f, exponent) powm_int(res##_x, res##_1, f##_x, f##_1, (exponent), MODULUS)
#define poly_invert_int(res, f) invert_int(res##_x, res##_1, f##_x, f##_1, MODULUS)
#define poly_eq_int(f, g) (f##_x == g##_x && f##_1 == g##_1)
#define poly_mul_x_int(res, f) mult_x_mod_int(res##_x, res##_1, f##_x, f##_1, MODULUS)
#define poly_pow_x_int(res, exponent) power_of_x_int(res##_x, res##_1, (exponent), MODULUS)
#define poly_sigma_int(res, f) sigma_int(res##_x, res##_1, f##_x, f##_1, MODULUS)
/* Initialises the random number generator using a (static) seed. */
int init_int(void);
/* Replacements for some GMP functions. */
#define even(n) ((n) % 2lu == 0)
#define odd(n) ((n) % 2lu == 1)
/*
* Calculate the greatest common divisor of a and b using the Euclidean
* algorithm.
*/
uint64_t gcd(uint64_t a, uint64_t b);
/* Compute the jacobi symbol (x/y) of x over y. */
int jacobi(uint64_t x, uint64_t y);
/*
* Given an integer 0 ≤ n < 2³², find the largest integer r such that r² ≤ n.
*/
uint64_t int_sqrt(const uint64_t n);
/*
* Use the integer square root function to figure out whether a number is a
* perfect square.
*/
bool is_square(const uint64_t n);
/* This function generates a random integer between low and high. Both low and
* high are included. */
uint64_t get_random_int(uint64_t low, uint64_t high);
/* Calculate [s], [d] such that [n-1=2^s*d] where [d] is odd. */
void split_int(uint64_t *s, uint64_t *d, const uint64_t n);
#endif