Botan 3.8.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*/
93BigInt ct_divide_word(const BigInt& x, word y);
94
95/**
96* BigInt word modulo, const time variant
97*
98* This runs with control flow independent of the values of x/y.
99* Warning: the loop bounds still leaks the size of x.
100*
101* @param x a positive integer
102* @param y a non-zero word
103* @return r the remainder of x divided by y
104*/
106word ct_mod_word(const BigInt& x, word y);
107
108/**
109* BigInt modulo, const time variant
110*
111* Using this function is (slightly) cheaper than calling ct_divide and
112* using only the remainder.
113*
114* @param x a non-negative integer
115* @param modulo a positive integer
116* @return result x % modulo
117*/
119BigInt ct_modulo(const BigInt& x, const BigInt& modulo);
120
121} // namespace Botan
122
123#endif
#define BOTAN_TEST_API
Definition api.h:39
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:230
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:168
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:192
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:51
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:123
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:83
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119