Here is today’s first problem:

Let the public key be $(y, p, g) = (64, 101, 2)$. The El Gamal Digital Signature of $11$ is $(r, s) = (8, s)$, where $s=$?

• What is the El Gamal Signature Scheme?
  wikipedia: The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

  my notes:

  1. Public / Private Keys:
     A triple $(y, p, g)$, where $p$ is a prime number, $g$ is a generator for $\mathbb{Z}_{p}^{*}$ and $y \equiv g^x \pmod p$ where x is the private Key.

  2. Signing:
     The signature of a message $m$ is a pair $(r, s)$. Since this is a probabilistic signature scheme, in order to generate such a pair, the signer begins by choosing a random number $k$ such that $0 \ne k \ne p-1$ and $\gcd (k, p-1) = 1$. Then,

     $$\begin{aligned} r &\equiv g^{k} \pmod p \\ s &\equiv (m - xr)\cdot k^{-1} \pmod{(p-1)} \end{aligned}$$

  3. Verifying:
     Check that $g^{m} \equiv y^{r} r^{s} \pmod p$

  The equation for s in the Signing step was obtained as follows:

  $$\begin{aligned} g^m &\equiv y^r r^s \pmod p \\ g^m &\equiv g^{xr} g^{ks} \pmod p \\ g^m &\equiv g^{xr + ks} \pmod p \\ m &\equiv xr + ks \pmod{(p-1)} \\ s &\equiv (m - xr) k^{-1} \pmod{(p-1)} \end{aligned}$$

  The second-to-last step might be confusing. Since $g$ is a generator of $\mathbb{Z}_p^*$ and $p$ is a prime number, we have that

  $$g^z \equiv g^{z + (p-1)} \pmod p$$

  for any $z \in \mathbb{Z}$. In other words, the powers of $g$ are congruent modulo $p-1$.

For this problem, we need to find $s$. We already have the values of $m$,$r$ and $p$, which means we need the values of $x$ and $k$. Those can be found easily by examining these equations:

It is clear that $x=6$ and $k=3$. We can now find $s$ as,

Therefore, $s=21$ is the solution to this problem.

Let’s move on to the next one:

The Hadamard gate is applied to the two qubits of a 2-qubit system in state

What is the resulting state of the 2-qubit system?

My notes, this youtube video and this stackexchange answer allowed me to understand how we can apply a Hadamard gate to two qubits.

First, we can rewrite the given state of the 2-qubit system as:

Now we will apply the Hadamard operation on each of these qubits,

And finally take the tensor product of the output from the operation,

which is equivalent to $\lvert 00\rangle$, the solution to this problem.

Even though I was able to solve this problem, I do not know anything about quantum computing. It seems like a very cool subject and I’d love to read and learn more about it. Until next time!