I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out.
Compute all solutions of $x^2 + 4x - 21 \equiv 0\,\bmod\,33$
First, I factorised this equation to give $(x + 7)(x - 3)$, which gives me the solutions $-7$ and $3$. However, under the conditions of modular arithmetic, I know that adding or subtracting $33$ as many times as we like will also provide an answer of zero.
IE: Let's try x = 26. $$(26 + 7)(26 - 3) = 33 \times 23 \equiv 0\,\bmod\, 33$$
Thus, it becomes fairly obvious to see that solutions to this equation will take the form $[3]$ and $[26]$, where the square brackets denote congruence classes.
I was given the hint in class that we should try to make the brackets equal to the factors of 33 - IE; try and get to $11 \times 3$, for example. But I really can't see how this would work.
Any further input would be great, thank you!!
Answer
The general purpose approach to composite moduli is to use the Chinese remainder theorem and Hensel lifting.
That is, you factor the modulus into prime powers, solve the problem modulo each factor, then use the Chinese remainder theorem to reconstitute the result. Since you will probably have two solutions modulo $3$ and two solutions modulo $11$, you will probably have four solutions modulo $33$.
If the individual prime power factors are nontrivial, then you can usually solve the problem modulo the prime, and then use Hensel lifting to extend this to solutions modulo the prime power. But this doesn't apply to your problem, since $3$ and $11$ are already prime.
The hint, I think, is trying to exploit the fact that if $xy = 0 \bmod {33}$, then either:
- $x = 0 \bmod {33}$
- $y = 0 \bmod {33}$
- $x = 0 \bmod 3$ and $y = 0 \bmod 11$
- $x = 0 \bmod 11$ and $y = 0 \bmod 3$
but in my opinion, it's sort of a weird way to go about the problem.
No comments:
Post a Comment