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
Related Tags
modular-arithmetic × 356rsa × 106
elliptic-curves × 42
public-key × 30
discrete-logarithm × 26
finite-field × 22
prime-numbers × 19
encryption × 17
diffie-hellman × 17
group-theory × 17
implementation × 16
number-theory × 16
cryptanalysis × 14
factoring × 14
montgomery-multiplication × 11
algorithm-design × 10
homomorphic-encryption × 9
hash × 8
quadratic-residuosity × 8
signature × 7
one-time-pad × 6
attack × 6
elgamal-encryption × 6
known-plaintext-attack × 6
cryptographic-hardware × 5