Discrete Mathematics Homework #3

Author： Bi_Gu
发布时间：March 14, 2022
591 views
One comment
285 words
Categories：课堂笔记离散作业离散数学

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/93512903_p0.jpg","_blank")'><i class="fa fa-camera"></i>$\quad$ **芙洛伦 by Cenci** </button>

# Discrete Mathematics

## Homework #3

### 1.

Since that $q=\lfloor a/b\rfloor$, we have that $a=bq+r$, where $r\in\mathbb{Z}$ and $0\leq r<b$.

Now write $b$ and $q$ in binary representation, say, $b=(b_{m-1}\cdots b_1b_0)_2$, $q=(q_{n-1}\cdots q_1q_0)_2$,

where $b_{m-1}=q_{n-1}=1;b_i,q_j\in\{0,1\},0\leq i\leq m-2,0\leq j\leq n-2.$ So that

$ℓ(b)=m,ℓ(q)=n$; Meanwhile we have

$$
\begin{gather}
b=b_{m-1}2^{m-1}+\cdots+b_12^1+b_02^0,q=q_{n-1}2^{n-1}+\cdots+q_12^1+ q_02^0\\\Rightarrow 0\leq r<b<2^m\\
\Rightarrow
a\geq bq\geq2^{m-1}\cdot2^{n-1}=2^{m+n-2};\\
a\leq(2^m-1)(2^n-1)+b-1\leq2^{m+n}-2^m-2^n+1+2^m-1-1\\=2^{m+n}-2^n-1<2^{m+n}
\end{gather}
$$

So that

$$
\begin{gather}
2^{m+n-2}\leq a\leq2^{m+n}-1\Leftrightarrow m+n-1<ℓ(a)\leq m+n+1\\
\Rightarrow m+n-1\leqℓ(a)\leq m+n+1\\
\Leftrightarrowℓ(b)+ℓ(q)-1\leqℓ(a)\leqℓ(b)+ℓ(q)+1\\
\Leftrightarrowℓ(a)-ℓ(b)-1\leqℓ(q)\leqℓ(a)-ℓ(b)+1
\end{gather}
$$

**The proof is complete.**

### 2.

**Code:** *in python*

```python
a = int(input("Please input an integer a:"))
b = int(input("Please input an integer b:"))
a,b = max(a, b), min(a, b)
r_0 = a; r_1 = b
s_0 = 1; t_0 = 0; s_1 = 0; t_1 = 1;
while r_1 != 0:
    q = r_0 // r_1
    r_0, r_1 = r_1, r_0 % r_1
    s_0, s_1 = s_1, s_0 - s_1 * q 
    t_0, t_1 = t_1, t_0 - t_1 * q
print("gcd(a, b) = " + str(r_0))
print("s = " + str(s_0))
print("t = " + str(t_0))
```

**Output:**

```python
gcd(a, b) = 102262202503830191683665976357924162800502848850675283606551004842197730273708934273936924908884652672442256553135718443388434586536491331416984834824033197117759304330445010455165933739427704599295260946079885114808010341303339499946231480241490457444191096184251471380336624525729640680939684612642314760897
s = -49224356025570205752640369113197589784192495362440084201087757193437212741118960024592916678950802342924534115789543242617936510771866636258909484003508425128530601681164598597924839372243612858504002463817184486904388029971268441911219848844590762141055813365169533361189741247565502362579257453658280613873
t = 52693465174047597579174064083061206575761398656935114430811243560695066306956237700638467741380344513260983625906545194154800126707869242528199250303471171536207597896008405650134889458156325490296036336342644796958477425288398387518178265890700656305714837368523496597321973212197144244237647291270529201589
```

![](https://cdn.dabigu.xyz/QQ截图20220310225023.png)

### 3.

**Code:** *in python*

```python
a = int(input("Please input an integer a:"))
e = int(input("Please input an integer e:"))
n = int(input("Please input an integer n:"))
if bool(0 <= a and a <= n - 1) == False:
    raise ValueError("Please input the right value for a!")
bin_e = list(bin(e)[2:])
x = a
result = 1
for i in range(len(bin_e)):
    result = (result * (x ** int(bin_e[- 1 - i]))) % n
    x = (x * x) % n
print("a^e (mod n) = " + str(result))
```

**Output:**

```python
a^e (mod n) = 19489389945386041607071081817241920919542635233623116738469155055206259159226436938865465087133511096927509156841578783141212143489199923529097996539792654733505278706812520830942209991900318336435802408907249020763770922682237250909513951994814724102553142432605916650209186930443817371994324442380618239060899770209698997113410596399791595727394196009053367816731883686504687107181648321094994097671995305419040805120814031555590587098823477471474182303588141313811472082913287478579910489774659842657219793245954171847503170017151440737380478840189460378458005476484742953848813170374548455806977675820760128018344
```

![](https://cdn.dabigu.xyz/QQ截图20220310230342.png)

### 4.

$(1)$ First, we use the **Extended Euclidean Algorithm** to compute that

$d=\text{gcd}(17,23)=1$; $23\times3+17\times(-4)=1$, so that $t=(17)^{-1}(\text{mod }23)=-4$.

So that

$$
17x\equiv11(\text{mod }23)
\Leftrightarrow x\equiv \frac{11}{1}\cdot(-4)\equiv-44\equiv2(\text{mod }23).
$$

$(2)$ First, we use the **Extended Euclidean Algorithm** to compute that

$d=\text{gcd}(55,75)=5$; $t=(11)^{-1}(\text{mod }15)$; use the **Algorithm** on $(15,11)$ again and we get

$15\times3+11\times(-4)=1$, so that $t=-4$.

So that

$$
55x\equiv35(\text{mod }75)
\Leftrightarrow x\equiv\frac{35}{5}\cdot(-4)\equiv-28\equiv2(\text{mod }15).
$$

### 5.

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

Eve has the information that $c_1\equiv m^{e_1}(\text{mod }N),c_2\equiv m^{e_2}(\text{mod }N),$ and $\text{gcd}(e_1,e_2)=1$.

**Step 1.** He expresses $e_1$ and $e_2$ in the following way:

$$
\left\{
\begin{array}{l}
c_1\equiv m^{e_1}(\text{mod }N)\\c_2\equiv m^{e_2}(\text{mod }N)
\end{array}
\right.\Rightarrow
\left\{
\begin{array}{l}
m^{e_1}=k_1N+c_1\\m^{e_2}=k_2N+c_2
\end{array}
\right.\Rightarrow
\left\{
\begin{array}{l}
e_1=\log_m(k_1N+c_1)\\e_2=\log_m(k_2N+c_2)
\end{array}
\right.
$$

**Step 2.** Since $\text{gcd}(e_1,e_2)=1$, he can use the **Extended Euclidean Algorithm** to compute $s,t$ which makes $e_1s+e_2t=1.$

**Step 3.** Using the information above he can express $m$ further:

$$
\begin{align}
m&=m^1=m^{e_1s+e_2t}=m^{e_1s}\cdot m^{e_2t}\\
&=m^{s\log_m(k_1N+c_1)}\cdot m^{t\log_m(k_2N+c_2)}\\
&=(k_1N+c_1)^s\cdot(k_2N+c_2)^t

\end{align}
$$

**Step 4.** Since that $st<0$, we may assume that $s<0$. Then,

$$
\begin{align}
m\cdot(k_1N+c_1)^{-s}&=(k_2N+c_2)^t\\
\Leftrightarrow m\cdot(k_1N+c_1)^{-s}&\equiv(k_2N+c_2)^t(\text{mod }N)\\
\Leftrightarrow m\cdot c_1^{-s}&\equiv c_2^t(\text{mod }N)
\end{align}
$$

Let $c_0=(c_1^{-s})^{-1}(\text{mod }N)$, so that

$$
m\equiv c_0\cdot c_2^t(\text{mod }N).
$$

**Step 5.** Since that $0\leq m<N$ and $\text{gcd}(m,N)=1$, there exists and only exists **one** solution $m$, which is what Eve wants to acquire.

Last modification：March 14, 2022

Support if you like my work! qwq

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

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

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

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

随机文章 Maths Analysis II - Section 8.1 Maths Analysis II - Section 8.3 Maths Analysis II - Homework #4 20220224

One comment

Windows 10 / Google Chrome clmylxizzm
November 27th, 2024 at 07:52 pm

你的才华让人惊叹，你是我的榜样。 https://www.4006400989.com/qyvideo/54568.html

Reply

Discrete Mathematics Homework #3

Bi_Gu • 2022 年 03 月 14 日

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/93512903_p0.jpg","_blank")'><i class="fa fa-camera"></i>$\quad$ **芙洛伦 by Cenci** </button>

# Discrete Mathematics

## Homework #3

### 1.

Since that $q=\lfloor a/b\rfloor$, we have that $a=bq+r$, where $r\in\mathbb{Z}$ and $0\leq r<b$.

Now write $b$ and $q$ in binary representation, say, $b=(b_{m-1}\cdots b_1b_0)_2$, $q=(q_{n-1}\cdots q_1q_0)_2$,

where $b_{m-1}=q_{n-1}=1;b_i,q_j\in\{0,1\},0\leq i\leq m-2,0\leq j\leq n-2.$ So that

$ℓ(b)=m,ℓ(q)=n$; Meanwhile we have

So that

**The proof is complete.**

### 2.

**Code:** *in python*

**Output:**

![](https://cdn.dabigu.xyz/QQ截图20220310225023.png)

### 3.

**Code:** *in python*

**Output:**

![](https://cdn.dabigu.xyz/QQ截图20220310230342.png)

### 4.

$(1)$ First, we use the **Extended Euclidean Algorithm** to compute that

$d=\text{gcd}(17,23)=1$; $23\times3+17\times(-4)=1$, so that $t=(17)^{-1}(\text{mod }23)=-4$.

So that

$$
17x\equiv11(\text{mod }23)
\Leftrightarrow x\equiv \frac{11}{1}\cdot(-4)\equiv-44\equiv2(\text{mod }23).
$$

$(2)$ First, we use the **Extended Euclidean Algorithm** to compute that

$d=\text{gcd}(55,75)=5$; $t=(11)^{-1}(\text{mod }15)$; use the **Algorithm** on $(15,11)$ again and we get

$15\times3+11\times(-4)=1$, so that $t=-4$.

So that

$$
55x\equiv35(\text{mod }75)
\Leftrightarrow x\equiv\frac{35}{5}\cdot(-4)\equiv-28\equiv2(\text{mod }15).
$$

### 5.

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

Eve has the information that $c_1\equiv m^{e_1}(\text{mod }N),c_2\equiv m^{e_2}(\text{mod }N),$ and $\text{gcd}(e_1,e_2)=1$.

**Step 1.** He expresses $e_1$ and $e_2$ in the following way:

**Step 2.** Since $\text{gcd}(e_1,e_2)=1$, he can use the **Extended Euclidean Algorithm** to compute $s,t$ which makes $e_1s+e_2t=1.$

**Step 3.** Using the information above he can express $m$ further:

$$
\begin{align}
m&=m^1=m^{e_1s+e_2t}=m^{e_1s}\cdot m^{e_2t}\\
&=m^{s\log_m(k_1N+c_1)}\cdot m^{t\log_m(k_2N+c_2)}\\
&=(k_1N+c_1)^s\cdot(k_2N+c_2)^t

\end{align}
$$

**Step 4.** Since that $st<0$, we may assume that $s<0$. Then,

Let $c_0=(c_1^{-s})^{-1}(\text{mod }N)$, so that

$$
m\equiv c_0\cdot c_2^t(\text{mod }N).
$$

**Step 5.** Since that $0\leq m<N$ and $\text{gcd}(m,N)=1$, there exists and only exists **one** solution $m$, which is what Eve wants to acquire.

Discrete Mathematics Homework #3

One comment

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

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

Introduction to Machine Learning Homework #2

Probability and Mathematic Stastics Homework #1

Discrete Mathematics Homework #11

Linear Algebra Notes - Section 1.4

Probability and Mathematic Stastics Lecture #1 Probability and Counting

Maths Analysis II - Homework #23 20220519

Linear Algebra Notes - Section 2.2

Discrete Mathematics Homework #3