Frank Day

Answered

2022-07-09

Simple question about number theory in CLRS book

This is theorem 11.5 from CLRS book. Suppose $a\in {\mathbb{Z}}_{p}^{\ast},b\in {\mathbb{Z}}_{p}$.

Consider two distinct keys k and l from ${\mathbb{Z}}_{p}$, so that $k\ne l$. For a given hash function ${h}_{ab}$ we let

$r=ak+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$

$s=al+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$

We first note that $r\ne s$. Why? Observe that

$r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p).$

I'm not very well familiar with Number Theory, so my question is why $r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)$ is correct?

This is theorem 11.5 from CLRS book. Suppose $a\in {\mathbb{Z}}_{p}^{\ast},b\in {\mathbb{Z}}_{p}$.

Consider two distinct keys k and l from ${\mathbb{Z}}_{p}$, so that $k\ne l$. For a given hash function ${h}_{ab}$ we let

$r=ak+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$

$s=al+b\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$

We first note that $r\ne s$. Why? Observe that

$r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p).$

I'm not very well familiar with Number Theory, so my question is why $r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)$ is correct?

Answer & Explanation

Dobermann82

Expert

2022-07-10Added 15 answers

Step 1

According to Knuth's definition for the mod operation, we have $\begin{array}{r}amodn=a-n\lfloor \frac{a}{n}\rfloor \end{array}$

And with the general definition of Congruence, $a\equiv b\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$ can be rewritten as $\begin{array}{r}a-b=kn\end{array}$.

We then have $\begin{array}{rl}r& =ak+bmodp=ak+b-p\lfloor \frac{ak+b}{p}\rfloor \\ s& =al+bmodp=al+b-p\lfloor \frac{al+b}{p}\rfloor \end{array}$

Subtract r by s, we have

$\begin{array}{}\text{(A)}& r-s=a(k-l)-p(\lfloor \frac{ak+b}{p}\rfloor +\lfloor \frac{al+b}{p}\rfloor )\end{array}$

With the definition of congruence quoted above, we can then rewrite (A) as $\begin{array}{r}r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)\end{array}$.

Hope this eliminates your doubts.

According to Knuth's definition for the mod operation, we have $\begin{array}{r}amodn=a-n\lfloor \frac{a}{n}\rfloor \end{array}$

And with the general definition of Congruence, $a\equiv b\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$ can be rewritten as $\begin{array}{r}a-b=kn\end{array}$.

We then have $\begin{array}{rl}r& =ak+bmodp=ak+b-p\lfloor \frac{ak+b}{p}\rfloor \\ s& =al+bmodp=al+b-p\lfloor \frac{al+b}{p}\rfloor \end{array}$

Subtract r by s, we have

$\begin{array}{}\text{(A)}& r-s=a(k-l)-p(\lfloor \frac{ak+b}{p}\rfloor +\lfloor \frac{al+b}{p}\rfloor )\end{array}$

With the definition of congruence quoted above, we can then rewrite (A) as $\begin{array}{r}r-s\equiv a(k-l)\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)\end{array}$.

Hope this eliminates your doubts.

daktielti

Expert

2022-07-11Added 2 answers

Explanation:

I’m turning my comment into an answer. If $r=ak+b$ mod p, and $s=al+b$ mod p, then $r-s=(ak+b)-(al+b)$ mod p, thus $r-s=ak-al$ mod p, hence $r-s=a(k-l)$ mod p.

I’m turning my comment into an answer. If $r=ak+b$ mod p, and $s=al+b$ mod p, then $r-s=(ak+b)-(al+b)$ mod p, thus $r-s=ak-al$ mod p, hence $r-s=a(k-l)$ mod p.

Most Popular Questions