0
$\begingroup$

I should prove mathematically that:

$D_k(E_k(p))=p$

I know

$E_k(p)=c=(p+k)\bmod26$

and

$D_k(c)=p=(c-k)\bmod26$

Substituting the two formulas to the initial assertion I have

$((p+k)\bmod26-k)\bmod26=p$

And applying the $\bmod$ property twice I have

$((p \bmod26+k \bmod26)\bmod26)-k)\bmod26=p$

$((p\bmod26+k\bmod26)\bmod26)\bmod26-k\bmod26)\bmod26=p$

But from here? How can I get rid of all that bunch of $\bmod$ to have $p$?

$\endgroup$
  • 1
    $\begingroup$ As a hint, in the modular arithmetic, instead of taking multiple mods you can do it once. math.stackexchange.com/questions/27336/… $\endgroup$ – Mahdi Feb 28 at 15:30
  • $\begingroup$ Hint: $a\bmod n$ is defined to be $x$ with $0\le x<n$ and $a-x$ a multiple of $n$. And it holds $0\le p<26$. $\endgroup$ – fgrieu Feb 28 at 15:42
2
+50
$\begingroup$

The lemma you need for this is that $$((a \bmod m) + b) \bmod m = (a + b) \bmod m \tag{1}$$ for all integers $a$, $b$ and for all positive integers $m$. In other words, this lemma says that, if you're going to add (or subtract) a bunch of numbers together and then reduce the sum modulo $m$, it doesn't matter whether or not you reduce any (or all) of the summands modulo $m$ first.


The easiest (and most usefully generalizable) way to prove the lemma (1) above is via the notion of modular congruence. Basically, we define $a$ and $b$ to be congruent modulo $m$, written as $a \equiv b \pmod m$, if $a = b + km$ for some integer $k$. From this definition, it immediately follows that $$(a \bmod m) \equiv a \pmod m$$ and, in fact, that $$(a \bmod m) = (b \bmod m) \iff a \equiv b \pmod m.$$

We can also show that the modular congruence relation $\equiv$ obeys many of the same algebraic laws as normal equality. In particular, we can show that it is transitive, i.e. that $$a \equiv b \text{ and } b \equiv c \implies a \equiv c \pmod m,$$ and that it is compatible with addition in the sense that $$a \equiv b \iff a + c \equiv b + c \pmod m.$$

Applying these properties of modular congruence, we can see that $(a \bmod m) \equiv a \pmod m$ implies $(a \bmod m) + b \equiv a + b \pmod m$, which then implies lemma (1).

Bonus exercise: Also show that modular congruence is compatible with multiplication in the sense that $$a \equiv b \implies ac \equiv bc \pmod m.$$


Now that we've proven lemma (1), the rest is simple: $$\begin{aligned} D_k(E_k(p)) &= ((p + k) \bmod 26) - k) \bmod 26 \\ &= (p + k - k) \bmod 26 \\ &= p \bmod 26. \end{aligned}$$ If $0 \le p < 26$, then $p \bmod 26 = p$, and we're done. (We do need to make this additional assumption for the encryption to be reversible, since it would not hold if $p$ could take other values!)


Of course, we could've also skipped lemma (1) entirely, and just appealed directly to modular congruence, and in particular to the fact that $$E_k(p) = (p + k) \bmod 26 \equiv p + k \pmod{26}\,\,$$ and $$D_k(c) = (c - k) \bmod 26 \equiv c - k \pmod{26},$$ from which it follows that $$D_k(E_k(p)) \equiv p + k - k = p \pmod{26}.$$

| improve this answer | |
$\endgroup$
0
$\begingroup$

I try to explain it with more details. Suppose we have the following modular equation. $$a \equiv b \mod(c)$$ Then for an integer $k$ we have, $$a=b+k \cdot c$$ For example, in $\mod(26)$ the reminder for $28$ is equal to $2$ and also it is the same reminder for all $2+k \cdot 26$ including $\{2,28,44,80,...\}$. At this point we need to figure out what is the case of addition and multiplication. So I claim, $$a_1 \mod(c)+ a_2 \mod(c)\equiv (a_1+a_2) \mod(c)$$ $$a_1 \mod(c)\cdot a_2 \mod(c)\equiv (a_1 \cdot a_2) \mod(c)$$ Proof: Let in the left side we have, $$a_1 \equiv b_1 \mod(c) , \: a_2 \equiv b_2 \mod(c)$$ We can write, $$a_1+a_2=b_1+b_2+(k_1+k_2)\cdot c$$ Assume $k_3=k_1+k_2$ as a new integer, $$a_1+a_2=b_1+b_2+k_3\cdot c \to a_1+a_2\equiv b_1+b_2 \mod(c)$$ Whence, $$a_1 \mod(c)+ a_2 \mod(c)\equiv (a_1+a_2) \mod(c)$$ More simply, the integer scalar is additive and you can execute the modular arithmetic once. We have the same way of proof for the multiplication. You can take the new scalar of c is the multiplication of multiple ones.

Let follow the simple example. $28\equiv 2 \mod(26)$ and also $32 \equiv 6 \mod(26)$. Then we have $28+32=60 \equiv 8 \mod(26)$ while it has the same result when you first calculate the modulu and then add them up.

I claim $28 \cdot 32 \equiv (2\cdot 6=12) \mod(26)$ while you can check it by multiplying them in advance and then find the remainder. Because $28\cdot 32= 896=34\cdot 26+12$.

As a conclusion, you don't need to care multiple mods and just do the operation first and then take the mod of the result.

Moreover, for more details have a look at this link, https://brilliant.org/wiki/modular-arithmetic/

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is misusing notations. A) $a \equiv b \mod(c)$: parenthesis are misplaced. This should be $a \equiv b \pmod c$. B) $a_1 \mod(c)+ a_2 \mod(c)\equiv (a_1+a_2) \mod(c)$ : too much space before the first two $\text{mod}$, superfluous parenthesis around $c$, and issue A on the right. This should be $(a_1 \bmod c)+(a_2 \bmod c) \equiv (a_1+a_2) \pmod c$ or something on that tune. Notice that the lack of parenthesis immediately on the left of a $\bmod$ is what shows that is an operatord, wth $a\bmod n$ possibly defined to be the (single) $x$ in range $[0,n)$ with $n$ dividing $a-x$. $\endgroup$ – fgrieu Mar 3 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.