Modular arithmetic and inverse functions

Question

The question is shown below:

Suppose $S=\{0,1,2,3,4,5,6,7,8,9,10\}$ and that the function $f:S\rightarrow S$ is given by:

$f(x)=6x^2+3x+8$ (mod 11)

Let $T=\{0,5\}$.

Find $f^{-1}\left(T\right)$.

Alright,

so my initial approach with this question was to find the inverse function,

$f^{-1}(x)=\dfrac{\pm\sqrt{24x-183}-3}{12}$, but $f^{-1}x\in S\geq0$

thus,

$f^{-1}(x)=\dfrac{\sqrt{24x-183}-3}{12}$

and then just churn out congruent values of $x=0,5$ in modulo 11 until I find a suitable value for $f^{-1}(x)$ within $S$, but it seems a bit tedious. Anyways, I repeated this churning process until I received the values of $\{2,3,6,10\}$.

Can anyone suggest a faster approach and please advise me if my approach is logically sound.

Many thanks :)

Answer 1

Considering the quadratic $f(x)=6x^2 + 3x + 8$ we have a discriminant (in $\Bbb F_{11}$) of

$$D=3^2 - 4 \cdot 6 \cdot 8 \equiv 4 \pmod{11}$$

which is a square (whether it is $\ge 0$ or not is irrelevant, and we don't use $\sqrt{D}$ in finite fields. We just have the two roots $2, -2 \equiv 9$. So $f(x)$ has two roots $$\frac{-3 + 2}{12} = -1 \equiv 10 \text{ and } \frac{-3 -2}{12} = -5 \equiv 6$$

where we have to remember that $12 \equiv 1 \pmod{11}$ which is helpful.

So modulo $11$ we have that $f(x)=(x+1)(x+5)$ and we've already found two members of $f^{-1}[\{0,5\}]$ namely the roots $10$ and $6$.

Next solve $f(x)=10$ (see below for the correct value) or equivalently $$6x^2 + 3x -2 = 0$$ which has discriminant $$3^2 - 4\cdot 6 \cdot (-2) = 2 \pmod{11}$$ and $2$ is not a square modulo $11$ (the squares in $\Bbb F_{11}$ are $0^2= 0,1^2=1, 2^2=4, 3^2= 9, 4^2=5, 5^2=3, 6^2=3, 7^2=5, 8^2=9,9^2=4,10^2=1$ or use quadratic reciprocity theory, if you know it. So $f$ does not assume the value $10$.

Solve $f(x)=5$ or $6x^2 + 3x+ 3= 0$, discriminant $3^2 - 4\cdot 6 \cdot 3 \equiv 3 \pmod{11}$ which is $5^2$ and $(-5)^2 = 6^2$ so roots are

$$\frac{-3 + 5}{12}=2, \frac{-3+6}{12}=3 \pmod{11}$$

so $$f^{-1}[\{0,5\}] = \{2,3,6,10\}$$ without tedious brute force.

Answer 2

If $\ a\equiv \alpha^2\pmod{11}\ $ is a quadratic residue $\mod{11}\ $, then $$ a^6 \equiv \alpha^{12}\equiv \alpha^2\equiv a\pmod{11}\ , $$ so the square roots of $\ a\pmod{11}\ $ are $\ \pm a^3\pmod{11}\ $.

If $\ y\equiv 6x^2+3x+8\pmod{11}\ $ then $\ 2y+4\equiv$$ x^2+6x+9$$\equiv(x+3)^2 \pmod{11}\ $ must be a quadratic residue, so $\ (2y+4)^3\equiv$$\pm(x+3) \pmod{11}\ $, and $\ x\equiv$$\pm(2y+4)^3-3\pmod{11}\ $.

Substituing $\ y=0\ $ in this expression gives $\ x\equiv$$ \pm4^3-3\equiv$$6,10\pmod{11}\ $. Substituting one of $\ x=6,10\ $ back into the polynomial $\ 6x^2+3x+8\ $ shows that it is indeed congruent to $\ 0\mod11\ $ for both of them (this check is necessary for at least one of these two values, to eliminate the possibility that $\ 2\cdot5+4\ $ might have been a quadratic non-residue $\mod 11\ $).

Similarly, substituting $\ y=5\ $ into the expression for $\ x\ $ gives $\ x\equiv$$\pm3^3-3\equiv$$2,3\pmod{11}\ $, which again can be shown to satisfy the congruence $\ 5\equiv 6x^2+3x+8\pmod{11}\ $. Thus, $\ f^{-1}\left(\{0,5\}\right)=$$\{2,3,6,10\}\ $, as you've already established.