Botan 3.7.1
Crypto and TLS for C&
divide.h
Go to the documentation of this file.
1/*
2* Division
3* (C) 1999-2007 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#ifndef BOTAN_DIVISON_ALGORITHM_H_
9#define BOTAN_DIVISON_ALGORITHM_H_
10
11#include <botan/bigint.h>
12
13namespace Botan {
14
15/**
16* BigInt Division
17* @param x an integer
18* @param y a non-zero integer
19* @param q will be set to x / y
20* @param r will be set to x % y
21*/
23void vartime_divide(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r);
24
25/**
26* BigInt division, const time variant
27*
28* This runs with control flow independent of the values of x/y.
29* Warning: the loop bounds still leak the sizes of x and y.
30*
31* @param x an integer
32* @param y a non-zero integer
33* @param q will be set to x / y
34* @param r will be set to x % y
35*/
37void ct_divide(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r);
38
39/**
40* BigInt division, const time variant, 2^k variant
41*
42* This runs with control flow independent of the value of y.
43* This function leaks the value of k and the length of y.
44* If k < bits(y) this returns zero
45*
46* @param k an integer
47* @param y a positive integer
48* @return q equal to 2**k / y
49*/
51BigInt ct_divide_pow2k(size_t k, const BigInt& y);
52
53/**
54* BigInt division, const time variant
55*
56* This runs with control flow independent of the values of x/y.
57* Warning: the loop bounds still leak the sizes of x and y.
58*
59* @param x an integer
60* @param y a non-zero integer
61* @return x/y with remainder discarded
62*/
63inline BigInt ct_divide(const BigInt& x, const BigInt& y) {
64 BigInt q, r;
65 ct_divide(x, y, q, r);
66 return q;
67}
68
69/**
70* Constant time division
71*
72* This runs with control flow independent of the values of x/y.
73* Warning: the loop bounds still leaks the size of x.
74*
75* @param x an integer
76* @param y a non-zero integer
77* @param q will be set to x / y
78* @param r will be set to x % y
79*/
81void ct_divide_word(const BigInt& x, word y, BigInt& q, word& r);
82
83/**
84* Constant time division
85*
86* This runs with control flow independent of the values of x/y.
87* Warning: the loop bounds still leaks the size of x.
88*
89* @param x an integer
90* @param y a non-zero word
91* @return quotient floor(x / y)
92*/
93inline BigInt ct_divide_word(const BigInt& x, word y) {
94 BigInt q;
95 word r;
96 ct_divide_word(x, y, q, r);
97 BOTAN_UNUSED(r);
98 return q;
99}
100
101/**
102* BigInt word modulo, const time variant
103*
104* This runs with control flow independent of the values of x/y.
105* Warning: the loop bounds still leaks the size of x.
106*
107* @param x a positive integer
108* @param y a non-zero word
109* @return r the remainder of x divided by y
110*/
112word ct_mod_word(const BigInt& x, word y);
113
114/**
115* BigInt modulo, const time variant
116*
117* Using this function is (slightly) cheaper than calling ct_divide and
118* using only the remainder.
119*
120* @param x a non-negative integer
121* @param modulo a positive integer
122* @return result x % modulo
123*/
125BigInt ct_modulo(const BigInt& x, const BigInt& modulo);
126
127} // namespace Botan
128
129#endif
#define BOTAN_TEST_API
Definition api.h:39
#define BOTAN_UNUSED
Definition assert.h:118
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:219
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:157
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:48
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:120
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:80