New answers tagged modular-arithmetic
2
Using that $\forall x\in\mathbb Z$, it holds $x\bmod p\,=\,p-1-((-x-1)\bmod p)$, and that in so-called two's-complement arithmetic $-x-1$ is the bitwise complement of $x$, the other answer's code simplifies to:
uint32_t imod(uint32_t x, uint32_t p) {
uint32_t s = -(x>>31); // 0 or -1, with the later iff x<0
x = x ^ s; ...
2
This answer answers Q1, as there may be merit other than just for calculating CRT RSA (e.g. the extended Euclidean algorithm).
Let's build it step-by-step.
First let's assume you've implemented the % operator for unsigned modular arithmetic in constant time, when you encounter a negative number x, we have the following:
x === -(-x)
Introducing the modulus p,...
1
Consider $f: x\mapsto f(x)=\underbrace{x+x\ldots x}_{a\text{ times}}+b\bmod 2^{32}$ in the the ring $(\mathbb Z_{2^{32}},+,\times)$, where $a$ and $b$ are constants.
Per one meaning, $f$ is linear, that is of the form $x\mapsto a\times x+b$, for constants $a$ and $b$. Per another meaning, $f$ is not (in general) a linear boolean function. $f$ is also not ...
Top 50 recent answers are included
