New answers tagged modular-arithmetic
2
Given $$\alpha ^{k}\equiv \prod p_{i}^{a^{i}} \mod p$$
take $\log$ of both sides to base $\alpha$
\begin{align}
\log_\alpha(\alpha ^{k}) &\equiv \log_\alpha(\prod p_{i}^{a^{i}}) \mod p\\
k &\equiv \sum \log_\alpha(p_{i}^{a^{i}}) \mod p-1 \quad\text{;by Little Fermat}\\
k &\equiv \sum a_i \log_\alpha(p_{i}) \mod p-1\\
\end{align}
Here $\...
1
Probably what your professor meant is that you start with any group element $\alpha$, and then use $g := \alpha^t$ as the generator for a cryptosystem such as Schnorr signatures, as long as $g$ is not itself the identity.
Why? If $g \ne 1$, then $g$ is guaranteed to have prime order $q$, because $g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$, ...
2
The point is that even though $p - 1 = tq$ may be large, the discrete log security of $(\mathbb Z/p\mathbb Z)^\times$ against Pohlig–Hellman depends on the size of $q$, not on the (possibly much larger) size of $p$ or $tq$. If $q$ is the largest prime factor, then the cost of computing discrete logs modulo $p$ is essentially at most the cost of computing ...
1
I think that Antoine Joux said modulo 4 just because he is explicitly working with two bits (the least significant for the xor and the most significant for the and), although that equation really holds over $\mathbb{Z}$ even if you reduce mod 3, as you noticed.
Indeed, in some point of the paper he even defines a function to extract a bit homomorphically.
...
0
Let $p = 2^{255} - 19$.
Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$. (Here $k = 1$.)
So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\...
1
"Integers modulo 4" is usually the finite ring $(\Bbb Z_4,+,*)$ which internal laws are
+ | 0 1 2 3 * | 0 1 2 3
--+-------- --+--------
0 | 0 1 2 3 0 | 0 0 0 0
1 | 1 2 3 0 1 | 0 1 2 3
2 | 2 3 0 1 2 | 0 2 0 2
3 | 3 0 1 2 3 | 0 3 2 1
but here, the question's citation only deals with the finite group $(\Bbb Z_4,+)$.
difference ...
6
Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python;
def fast_power(base, power):
result = 1
while power > 0:
# If power is odd
if power % 2 == 1:
result = (result * base) % MOD
# Divide the power by 2
power = ...
1
Yes. You don't need to wait until the end of the computation to compute the remainder, you can do that in each step of the exponentiation; this way, the largest numbers you'll need to handle are twice the size of n.
There are many algorithms to compute the exponentiation itself, the simplest is square-and-multiply.
Top 50 recent answers are included
