New answers tagged

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