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