Tag Info

New answers tagged


Fkraiem's answer is correct: this is not necessary. From your comment on his answer it seems however you don't understand why Alice and Bob retrieve the same key. This, again, doesn't rely on $g$ being a generator. Recall from your high school math classes that $(g^a)^b = g^{ab} = g^{ba} = (g^b)^a$. This is basically the trick that is being used here. Since ...


It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.


Actually, it doesn't matter (as long as the polynomial is prime, of course). For any $n$, there's only one finite field $GF(2^n)$, however there are a number of ways of mapping those elements to bit patterns. We call that mapping a representation; one method of generating such a representation is to use a prime polynomial of degree $n+1$. Now, between any ...


Claim. $a^{(p-1)/2} = 1$ if and only if $x$ is even. Proof. If $x$ is even, let $x = 2y$. Then $$a^{(p-1)/2} = (g^x)^{(p-1)/2} = g^{2y(p-1)/2} = (g^{p-1})^y = 1^y = 1.$$ If $x$ is odd, let $x = 2y+1$. Then $$a^{(p-1)/2} = g^{(2y+1)(p-1)/2} = \dots$$ (remember here that $g$ is a generator of $\mathbf{F}_p^*$).


It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$. However, there are cases for which ...


if you know a, you also know $\frac{1}{a}$ then $g=(g^a)^{\frac{1}{a}}$ UPDATE: answering the question for solving $X^r - a = 0$, when r | (p-1). If my analysis is correct: if r | (p-1): the square root algorithm can easily be adapted regarding the form of prime p. If p=2.r.q + 2.r -1: this deterministic case: Let Let $y_0=a^{\frac{p+1}{2 \times r}} ...

Top 50 recent answers are included