Discrete Mathematics Homework #4

Author： Bi_Gu
发布时间：March 18, 2022
459 views
No comments
2021 words
Categories：课堂笔记离散作业离散数学

# Discrete Mathematics

## Homework #4

### 1.

Since that 11,13,17 and 19 are all primes, it's obvious that they are pairwise relatively prime;

So that for the equation system in the problem, it always has a solution according to the **Chinese Remainder Theorem**.

Let $n_1=11,n_2=13,n_3=17,n_4=19$, then $n=n_1n_2n_3n_4=46189.$ Since that $N_i=n/n_i$, we have that $N_1=4199,N_2=3553,N_3=2717,N_4=2431.$

It's obvious that $\text{gcd}(N_i,n_i)=1$, so we solve out four pairs of $(s_i,t_i)$ that makes $s_iN_i+t_in_i=1$ respectively using the **Extended Euclidean Algorithm**:

$$
\begin{cases}
s_1=-4\\t_1=1527
\end{cases}\ ;
\begin{cases}
s_2=-3\\t_2=820
\end{cases}\ ;
\begin{cases}
s_3=-6\\t_3=959
\end{cases}\ ;
\begin{cases}
s_4=-1\\t_4=128
\end{cases}\ .
$$

So that

$$
b=\sum_{i=1}^4b_i(N_is_i)=-16796a_1-10659a_2-16302a_3-2431a_4
$$

Since the solutions are $[b]_N$, we have all the integer solutions of the required equation system to be

$$
[-16796a_1-10659a_2-16302a_3-2431a_4]_{46189}.
$$

### 2.

Eve **CAN** learn the value of $m$.

Eve has the information that $m^3\equiv c_1(\text{mod }N_1),m^3\equiv c_2(\text{mod }N_2),m^3\equiv c_3(\text{mod }N_3)$, and $N_1,N_2,N_3$ are pairwise relatively prime.

**Step 1.** Those equations always have a solution according to the **Chinese Remainder Theorem**, from which Eve can achieve:

$n=N_1N_2N_3;n_1=N_2N_3,n_2=N_1N_3,n_3=N_1N_2;\text{gcd}(N_i,n_i)=1(i=1,2,3).$

**Step 2.** He can now use the **Extended Euclidean Algorithm** to compute $s_i,t_i$ $\mathrm{s.t.}$ $s_in_i+t_iN_i=1(i=1,2,3).$

So that $b=\sum_\limits{i=1}^3c_is_in_i$, $m^3\equiv\sum_\limits{i=1}^3c_is_in_i(\text{mod }N_1N_2N_3)$.

Therefore $m^3$ can be expressed in the form

$m^3=c_1s_1N_2N_3+c_2s_2N_1N_3+c_3s_3N_1N_2+kN_1N_2N_3(k\in\mathbb{Z})$.

**Step 3.** Since that $0<m<N_i$ for $i=1,2,3$,

$$
\begin{array}{l}
0<m^3<N_1N_2N_3\Rightarrow 0<b+kN_1N_2N_3<N_1N_2N_3,\\
\text{There exists and only exists one solution for }k,\text{ which is}\\
k=-\lfloor\frac{b}{N_1N_2N_3}\rfloor.
\end{array}
$$

**Step 4.** So that Eve can acquire the only possible value of $m$

$$
m=\sqrt[3]{b-N_1N_2N_3\cdot\lfloor\frac{b}{N_1N_2N_3}\rfloor},\text{where }b=c_1s_1N_2N_3+c_2s_2N_1N_3+c_3s_3N_1N_2.
$$

### 3.

For all $a,b,c\in G$, we have that $a,b,c\in\mathbb{R}$ and $a,b,c>1$.

**Closure:** $ab-a-b+2\in\mathbb{R}$; $ab-a-b+2=(a-1)(b-1)+1>(1-1)(1-1)+1=1$,

so that $a\star b\in G$.

**Associative:**

$$
\begin{align}
(a\star b)\star c&=(ab-a-b+2)\star c=(ab-a-b+2)c-(ab-a-b+2)-c+2\\
&=abc-ac-bc-ab-a-b-c\\
&=(bc-b-c+2)a-(bc-b-c-2)-a+2=(bc-b-c+2)\star a\\
&=a\star(b\star c).
\end{align}
$$

**Identity:** Let $e=2\in G$, then $\forall a\in G$,

$$
2\star a=2a-a-2+2=a;\ a\star 2=a\cdot2-a-2+2=a.
$$

**Inverse:** Let $b=1\in G$, then $\forall a\in G$,

$$
1\star a=a-1-a+2=1;\ a\star1=a-a-1+2=1.
$$

From the above we achieve that the pair $(G,\star)$ is a group. Furthermore,

**Commutative:** $\forall a,b\in G$,

$$
a\star b=ab-a-b+2=ba-b-a+2=b\star a.
$$

So that the group $(G,\star)$ is an **Abelian group**.

**The proof is complete.**

### 4.

Since that the pair $(G,\cdot)$ is a multiplicative Abelian group of order $m$, according to the **Euler's Theorem**, for any $a\in G$, $a^m=1$.

For any $a\in G$, let $k$ be the least possible integer that satisfies $a^k=1$, then $1\leq k\leq m, k=o(a)$.

According to the **Division Algorithm**, $m$ can be expressed in the form $m=kq+r$ where $q,r\in\mathbb{Z},0\leq r<q$, thus $kq\leq m<(k+1)q$. Since that $a^k=1$, $a^{kq}=(a^k)^q=1^q=1$;

Meanwhile, $a^m=1$; so that $a^m/a^{kq}=a^{m-kq}=1=a^0\Leftrightarrow m=kq\Leftrightarrow k\mid m\Leftrightarrow o(a)\mid m$.

**The proof is complete.**

### 5.

**Code:** *in python*

```python
# inputs
p = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227998859
A = 112983575163002618947589666666735428181684517845144875096902910066434723952623016603393212501214127399908823223492478725971266042754892798177781267512821607470545283059472689034731313027619864228688466438258327552045437590203790635506728603774799021127049872571983254506993921153718739796769296097404717448108
B = 111772767805210239496365191691516881043394988196297062013853646674574743401042736447328886156429629192691601526398366088012736749454626686281467579205675084461989494513294624066074137247913037330040487275346913253345733429767781900977102687185378411660147190296412313303321533586102552123457499563789255321369
q = (p - 1) / 2
g = 3
# algorithm
a = 0; b = 0
while g ** a % p != A:
    a += 1
while g ** b % p != B:
    b += 1
ka = B ** a % p; kb = A ** b % p
#outputs
print("The output of Alice is " + str(ka))
print("The output of Bob is " + str(kb))
```

**Output:**

```python
The output of Alice is 10828112783453462381041707802056149866596392072243903940987459672779260675319522663099080388770903982546250524992420350200207624327420612300170620802665302905750045777684348125827484365007590718638373187936889967309324722655294992225815410914105072210725045953105019352457540772995508978315699107247398350128
The output of Bob is 10828112783453462381041707802056149866596392072243903940987459672779260675319522663099080388770903982546250524992420350200207624327420612300170620802665302905750045777684348125827484365007590718638373187936889967309324722655294992225815410914105072210725045953105019352457540772995508978315699107247398350128
```

![QQ截图20220317234953](https://cdn.dabigu.xyz/QQ%E6%88%AA%E5%9B%BE20220317234953.png)

Last modification：March 18, 2022

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/178/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

猜你想看 Discrete Mathematics Homework #13 Maths Analysis II - Homework #27 20220602 Maths Analysis II - Homework #26 20220531

随机文章 Discrete Mathematics Homework #2 Discrete Mathematics Homework #9 Discrete Mathematics Homework #4

Discrete Mathematics Homework #4

Bi_Gu • 2022 年 03 月 18 日

# Discrete Mathematics

## Homework #4

### 1.

Since that 11,13,17 and 19 are all primes, it's obvious that they are pairwise relatively prime;

So that for the equation system in the problem, it always has a solution according to the **Chinese Remainder Theorem**.

Let $n_1=11,n_2=13,n_3=17,n_4=19$, then $n=n_1n_2n_3n_4=46189.$ Since that $N_i=n/n_i$, we have that $N_1=4199,N_2=3553,N_3=2717,N_4=2431.$

It's obvious that $\text{gcd}(N_i,n_i)=1$, so we solve out four pairs of $(s_i,t_i)$ that makes $s_iN_i+t_in_i=1$ respectively using the **Extended Euclidean Algorithm**:

$$
\begin{cases}
s_1=-4\\t_1=1527
\end{cases}\ ;
\begin{cases}
s_2=-3\\t_2=820
\end{cases}\ ;
\begin{cases}
s_3=-6\\t_3=959
\end{cases}\ ;
\begin{cases}
s_4=-1\\t_4=128
\end{cases}\ .
$$

So that

$$
b=\sum_{i=1}^4b_i(N_is_i)=-16796a_1-10659a_2-16302a_3-2431a_4
$$

Since the solutions are $[b]_N$, we have all the integer solutions of the required equation system to be

$$
[-16796a_1-10659a_2-16302a_3-2431a_4]_{46189}.
$$

### 2.

Eve **CAN** learn the value of $m$.

Eve has the information that $m^3\equiv c_1(\text{mod }N_1),m^3\equiv c_2(\text{mod }N_2),m^3\equiv c_3(\text{mod }N_3)$, and $N_1,N_2,N_3$ are pairwise relatively prime.

**Step 1.** Those equations always have a solution according to the **Chinese Remainder Theorem**, from which Eve can achieve:

$n=N_1N_2N_3;n_1=N_2N_3,n_2=N_1N_3,n_3=N_1N_2;\text{gcd}(N_i,n_i)=1(i=1,2,3).$

**Step 2.** He can now use the **Extended Euclidean Algorithm** to compute $s_i,t_i$ $\mathrm{s.t.}$ $s_in_i+t_iN_i=1(i=1,2,3).$

So that $b=\sum_\limits{i=1}^3c_is_in_i$, $m^3\equiv\sum_\limits{i=1}^3c_is_in_i(\text{mod }N_1N_2N_3)$.

Therefore $m^3$ can be expressed in the form

$m^3=c_1s_1N_2N_3+c_2s_2N_1N_3+c_3s_3N_1N_2+kN_1N_2N_3(k\in\mathbb{Z})$.

**Step 3.** Since that $0<m<N_i$ for $i=1,2,3$,

**Step 4.** So that Eve can acquire the only possible value of $m$

$$
m=\sqrt[3]{b-N_1N_2N_3\cdot\lfloor\frac{b}{N_1N_2N_3}\rfloor},\text{where }b=c_1s_1N_2N_3+c_2s_2N_1N_3+c_3s_3N_1N_2.
$$

### 3.

For all $a,b,c\in G$, we have that $a,b,c\in\mathbb{R}$ and $a,b,c>1$.

**Closure:** $ab-a-b+2\in\mathbb{R}$; $ab-a-b+2=(a-1)(b-1)+1>(1-1)(1-1)+1=1$,

so that $a\star b\in G$.

**Associative:**

$$
\begin{align}
(a\star b)\star c&=(ab-a-b+2)\star c=(ab-a-b+2)c-(ab-a-b+2)-c+2\\
&=abc-ac-bc-ab-a-b-c\\
&=(bc-b-c+2)a-(bc-b-c-2)-a+2=(bc-b-c+2)\star a\\
&=a\star(b\star c).
\end{align}
$$

**Identity:** Let $e=2\in G$, then $\forall a\in G$,

$$
2\star a=2a-a-2+2=a;\ a\star 2=a\cdot2-a-2+2=a.
$$

**Inverse:** Let $b=1\in G$, then $\forall a\in G$,

$$
1\star a=a-1-a+2=1;\ a\star1=a-a-1+2=1.
$$

From the above we achieve that the pair $(G,\star)$ is a group. Furthermore,

**Commutative:** $\forall a,b\in G$,

$$
a\star b=ab-a-b+2=ba-b-a+2=b\star a.
$$

So that the group $(G,\star)$ is an **Abelian group**.

**The proof is complete.**

### 4.

Since that the pair $(G,\cdot)$ is a multiplicative Abelian group of order $m$, according to the **Euler's Theorem**, for any $a\in G$, $a^m=1$.

For any $a\in G$, let $k$ be the least possible integer that satisfies $a^k=1$, then $1\leq k\leq m, k=o(a)$.

According to the **Division Algorithm**, $m$ can be expressed in the form $m=kq+r$ where $q,r\in\mathbb{Z},0\leq r<q$, thus $kq\leq m<(k+1)q$. Since that $a^k=1$, $a^{kq}=(a^k)^q=1^q=1$;

Meanwhile, $a^m=1$; so that $a^m/a^{kq}=a^{m-kq}=1=a^0\Leftrightarrow m=kq\Leftrightarrow k\mid m\Leftrightarrow o(a)\mid m$.

**The proof is complete.**

### 5.

**Code:** *in python*

**Output:**

![QQ截图20220317234953](https://cdn.dabigu.xyz/QQ%E6%88%AA%E5%9B%BE20220317234953.png)

Discrete Mathematics Homework #4

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Probability and Mathematic Stastics Homework #1

Introduction to Machine Learning Homework #2

Linear Algebra Notes - Section 2.1

Maths Analysis II - Section 8.2

Maths Analysis II - Homework #25 20220526

Diary Set #0 20220214

Discrete Mathematics Homework #3

Discrete Mathematics Homework #4