$G$ is additive group $\bmod {88}$. $f$ is known element of subgroup order $8$. Proof that lowest 3 bits of $x$ can be inferred from $xf \bmod 88$.
$G$ is the additive group of integers modulo $88$.
This group contains one subgroup of order $8$ - these are the elements of this subgroup - $\{0, 11, 22, 33, 44, 55, 66, 77\}$.
$f$ is an element of this subgroup. $xf \bmod 88$ is essentially scalar multiplication of the element $f$ of the subgroup of order $8$. So $xf \bmod 88$ will be one of the elements of that subgroup.
I wrote a program where I used $f = 11$
for x in range(88):
varxf = (x*11)% 88
rem = x%8
print(str(varxf) + " " + f' {rem:08b}')
From the output it's clear that, for $f=11$
| $11.x$ | $x$ low 3 bits |
|---|---|
| 11 | 001 |
| 22 | 010 |
| 33 | 011 |
| 44 | 100 |
| 55 | 101 |
| 66 | 110 |
| 77 | 111 |
Likewise for other values of $f$, I can infer the lower $3$ bits of $x$ if I know $xf \bmod 88$.
Let me give an example.
If Person $A$ chooses $x = 10$ (I don’t know the value of $x$). $A$ then calculates $10 * 11 \bmod 88$ which is $22$ & gives me this value. The moment, I know 22, I then look at the table above & infer that the $x$ he chose had it’s last 3 bits as $010$
Instead if he chooses $x = 53$ & gives me $53*11 \bmod 88$ (i.e. $55$), I can again look at the table & figure out that he chose some $x$ whose last 3 bits were $101$.
I am trying to prove the above formally, that from $xe \bmod 88$, I can infer the lower $3$ bits of $x$
When I try to prove this, I see the following which may be relevant.
$\bmod 8$ (i.e. the remainder after dividing by $8$) is the lower $3$ bits of the number being divided/mod'ed.
$88$ is of the form $p * 2^{n}$ where $p$ is a prime & $p$ & $2^{n}$ are co-prime.
Because of the properties of cyclic subgroups, $11$ is a generator for subgroup of order $8$
$a \bmod {pq} = a \bmod p = a \bmod q$ (Opp of Chinese Remainder Theorem)
I have been trying this for a couple of days now, but I am unable to proceed beyond figuring out the above points.
I want to end up proving this for a group which is of the form $\bmod {p*2^{n}}$, but for the purpose of this question, I want to just prove it for these specific values $(11, 8, 88)$
$$x = 8q+r$$ $$f = 11g$$ $$\begin{array} {rcl} xf \bmod 88 &=& (8q+r)\cdot 11g \bmod 88 \\ &=& (88qg + 11rg) \bmod 88 \\ &=& 11(rg \bmod 8) \end{array}$$
So the question is, if someone gives you $(rg \bmod 8)$, can you find $r$? Depends on if $g$ is even. If $g = 4$ for example, then $r \in \{2, 4, 6\}$ will all give the same value $11(rg \bmod 8) = 0$. But for odd $g$, that is for $f \in \{11, 33, 55, 77\}$, then you can find $r$ because $g$ has a multiplicative inverse modulo $8$.