Simplified Fiat-Shamir example generates wrong output

Question

I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here.

Preparation:

1. Select 2 prime integers and their product:

   n = 19 * 23 = 437
   

2. Select s coprime to n:

   s = 242
   

3. Compute v:

   v = (s^2) % n = 6
   

Now the round:

1. Select random r between 1 and n - 1:

   r = 410
   

2. Calculate x:

   x = (r^2) % n = 292
   

3. Choose e either 0 or 1:

   e = 1
   

4. Calculate y:

   y = (r * s^e) % n = 21
   

Now if y^2 equals (x * v^e) % n then it's accepted. However in my case

y^2 = 441
(x * v^e) % n = 4

Why don't these numbers match? What am I doing wrong here?

Answer 1

The problem is one of notation for modular arithmetic, at the point of the question reading

if y^2 equals (x * v^e) % n then..

Likely the textbook is about

if $y^2\equiv x\cdot v^e\pmod n$ then..

By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 divides 441-4, thus $y^2\equiv x\cdot v^e\pmod n$ holds.

Sometime, $a\equiv b\pmod n$ is written as $a=b\pmod n$, but rigorously the later means that $a$ is the set of solutions to the former. $a\equiv b\mod n$ or $a=b\mod n$ are also used, but the later is best avoided, because it is dangerously close to $a=b\bmod n$, to be read as $a=(b\bmod n)$ and thus rigorously meaning $0\le a<n$ and $|b-a|$ is a multiple of $n$. However, only a strict Vulcan would assume $0\le y^2<n$ when seeing $y^2=b\bmod n$.

Note: On this site, $y^2\equiv x\cdot v^e\pmod n$ can be written as $y^2\equiv x\cdot v^e\pmod n$. A right-click on a rendered formula then Show Math As TeX Commands will reveal the T_EX code used. I often use this T_EX cheat sheet.