# Tag Info

5

The modulo operator keeps the result of the addition of $M$ and $K$ within the set $Z$. For example, if $m$ is 10, $M$ is 6 and $K$ is 5, $M + K$ would be 11 which is no longer in the set $Z$. Taking 11 mod 10 results in 1 which is in the set $Z$. As a help towards answering the question whether scheme $M + K$ mod $m$ is perfectly secure, when $m$ is 26 ...

2

In brief: If you know $(a,N)$, you can speed the computation up by precomputing some of the powers of $a$. Let $x=x_n\dots x_1x_0=\sum_{i=0}^n x_i 2^i$ be the binary expansion of $x$, and let $a_j=a^{2^j}\pmod N$. Very naively: $$a^x \pmod N = \overbrace{a*(a*(a*\dots*(a))\dots))}^{\text{x terms}}$$ This requires $\theta(x)$ multiplications. ...

4

One obvious way is to precompute values $a^{k_1} \bmod N$, $a^{k_2} \bmod N$, ...,$a^{k_i} \bmod N$, and (depending on the value of $x$) multiply together the appropriate elements. To take a simple example, if we precompute $a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N$, and (based on the value of $x$ in binary, multiply the appropriate ...

Top 50 recent answers are included