Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Tag Info

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