114 年 國立成功大學工程科學系碩士班己組《計算機概論》

核心觀念

本題綜合考查：

1. 矩陣快速冪與 Fibonacci 數列。
2. 遞迴定義與基底條件。
3. 最長遞增子序列（Longest Increasing Subsequence, LIS）。
4. Selection Sort、Insertion Sort 的實作、複雜度與實驗比較。

---

（1）利用矩陣快速冪計算 Fibonacci 數

定義與推導

Fibonacci 數列定義為：

$$F_0=0,\qquad F_1=1$$ $$F_n=F_{n-1}+F_{n-2}$$

可表示為矩陣關係：

$$\begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}$$

令

$$A= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$$

則：

$$\begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} = A^n \begin{bmatrix} F_1\\ F_0 \end{bmatrix}$$

因此，$A^n$ 的左下角元素就是 $F_n$。

矩陣快速冪

計算 $A^n$ 時使用二分冪：

• 若 $n=0$，結果為單位矩陣。
• 若 $n$ 為偶數，先計算 $A^{n/2}$，再平方。
• 若 $n$ 為奇數，先計算 $A^{n-1}$，再乘上 $A$。

Python 實作

def multiply(X, Y):
    return [
        [
            X[0][0] * Y[0][0] + X[0][1] * Y[1][0],
            X[0][0] * Y[0][1] + X[0][1] * Y[1][1]
        ],
        [
            X[1][0] * Y[0][0] + X[1][1] * Y[1][0],
            X[1][0] * Y[0][1] + X[1][1] * Y[1][1]
        ]
    ]


def matrix_power(A, n):
    result = [
        [1, 0],
        [0, 1]
    ]

    while n > 0:
        if n % 2 == 1:
            result = multiply(result, A)

        A = multiply(A, A)
        n //= 2

    return result


def fibonacci(n):
    if n < 0:
        raise ValueError("n 必須為非負整數")

    if n == 0:
        return 0

    A = [
        [1, 1],
        [1, 0]
    ]

    return matrix_power(A, n)[0][1]


print(fibonacci(10))  # 55

複雜度分析

矩陣指數每次約減半，因此需要 $O(\log n)$ 次矩陣乘法。由於本題矩陣固定為 $2\times2$，每次乘法皆為常數時間：

$$T(n)=O(\log n)$$

迴圈版本的額外空間為：

$$S(n)=O(1)$$

傳統遞迴：

def fibonacci_slow(n):
    if n <= 1:
        return n
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

會重複計算大量相同子問題，其時間複雜度約為：

$$O(2^n)$$

因此矩陣快速冪在 $n$ 很大時明顯有效率得多。

解題技巧

看到下列特徵時，可考慮矩陣快速冪：

• 遞迴關係是線性的。
• 需要計算非常大的第 $n$ 項。
• 題目要求優於 $O(n)$ 的演算法。

---

（2）以遞迴完成 func(n)

題意釐清

題目列出的數列為：

$$1,1,2,6,24,120,720,\ldots$$

這是階乘數列：

$$0!,1!,2!,3!,4!,5!,6!,\ldots$$

因此合理的函數定義為：

$$func(0)=1$$ $$func(n)=n\cdot func(n-1),\qquad n\geq1$$

題目文字寫成 func(2) = 6、func(3) = 24，與前述數列索引不一致；以下依數列及階乘定義，採用 func(2)=2、func(3)=6。

遞迴程式

def func(n):
    if n < 0:
        raise ValueError("n 必須為非負整數")

    if n == 0:
        return 1

    return n * func(n - 1)


n = 6
print(func(n))  # 720

執行推導

以 $n=4$ 為例：

$$func(4)=4\cdot func(3)$$ $$=4\cdot3\cdot func(2)$$ $$=4\cdot3\cdot2\cdot func(1)$$ $$=4\cdot3\cdot2\cdot1\cdot func(0)$$ $$=4\cdot3\cdot2\cdot1=24$$

複雜度分析

每次遞迴使 $n$ 減少 $1$，共呼叫 $n+1$ 層：

$$T(n)=O(n)$$

遞迴呼叫堆疊的空間為：

$$S(n)=O(n)$$

解題技巧

遞迴函數必須包含：

1. 基底條件，避免無限遞迴。
2. 每次呼叫都要朝基底條件前進。
3. 遞迴式必須符合數列的數學定義。

---

（3）最長遞增子序列 LIS

核心觀念

子序列不要求元素連續，只要求保留原本的相對順序。

例如：

[10, 9, 2, 5, 3, 7, 101, 18]

其中一組最長遞增子序列為：

[2, 3, 7, 101]

長度為 $4$。

本題採用 tails 方法：

• tails[k] 表示長度為 $k+1$ 的遞增子序列，其結尾元素的最小可能值。
• 對每個新元素，以二分搜尋找到第一個大於等於它的位置。
• 將該位置的值替換為較小的結尾值。

tails 的內容不一定本身就是最後的 LIS，但其長度一定等於 LIS 長度。

只求長度的實作

from bisect import bisect_left


def lis_length(nums):
    tails = []

    for x in nums:
        position = bisect_left(tails, x)

        if position == len(tails):
            tails.append(x)
        else:
            tails[position] = x

    return len(tails)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_length(nums))  # 4

執行流程

對數列：

10, 9, 2, 5, 3, 7, 101, 18

tails 的變化如下：

10
9
2
2, 5
2, 3
2, 3, 7
2, 3, 7, 101
2, 3, 7, 18

最後長度為 $4$。

若要求輸出實際子序列

核心觀念

本題綜合考查四個主題：

1. 增強型平衡搜尋樹：在維持排序的同時，額外記錄子樹大小，以支援區間計數。
2. 字典序排列：利用 pivot、交換與反轉，原地求下一個字典序排列。
3. AVL 樹：每個節點的左右子樹高度差不得超過 $1$。
4. 混合排序法：大區間使用 Quick Sort，小區間改用 Insertion Sort，以降低常數成本。

---

（1）支援插入、區間計數與刪除的資料結構

解題方法

採用「帶有子樹大小資訊的平衡二元搜尋樹」，例如 AVL Tree 或 Red-Black Tree。

每個節點除了儲存：

• 鍵值 key
• 左子樹與右子樹
• 平衡資訊

再增加：

$$size(v)=1+size(v.left)+size(v.right)$$

若允許重複元素，可在節點中增加 count，並將公式改為：

$$size(v)=count(v)+size(v.left)+size(v.right)$$

平衡樹可保證樹高為 $O(\log n)$。

---

1. Insert

插入元素時，依照二元搜尋樹規則尋找插入位置，沿途更新各節點的 size，最後透過 AVL 旋轉或 Red-Black Tree 的修正維持平衡。

時間複雜度：

$$O(\log n)$$

---

2. Count the number of elements within a range

欲計算區間 $[L,R]$ 中的元素數量，可使用：

$$count(L,R)=rank(\leq R)-rank(<L)$$

其中：

• $rank(\leq x)$：小於或等於 $x$ 的元素數量
• $rank(<x)$：嚴格小於 $x$ 的元素數量

計算 $rank(\leq x)$

從根節點開始：

• 若 $x<key(v)$，往左子樹尋找。
• 若 $x\geq key(v)$，則左子樹與目前節點都符合條件，累加：

$$size(v.left)+count(v)$$

再往右子樹尋找。

由於每次只沿著一條樹路徑前進，時間複雜度為：

$$O(\log n)$$

因此區間計數也是：

$$O(\log n)$$

---

3. Delete a specific element

依照二元搜尋樹規則尋找指定元素：

• 若沒有子節點，直接刪除。
• 若只有一個子節點，以子節點取代。
• 若有兩個子節點，以中序後繼或中序前驅取代，再刪除原節點。
• 沿途更新 size，並執行平衡修正。

時間複雜度：

$$O(\log n)$$

---

複雜度總結

操作	時間複雜度
Insert	$O(\log n)$
Range Count	$O(\log n)$
Delete	$O(\log n)$
額外空間	$O(n)$

解題技巧與常見陷阱

• 普通二元搜尋樹若退化成鏈狀，操作會變成 $O(n)$，因此必須使用平衡樹。
• 只使用 Heap 無法有效支援任意區間計數。
• 只使用 Hash Table 可快速插入與刪除，卻無法有效處理大小關係與區間查詢。
• 若只需靜態資料的區間計數，也可使用排序陣列加 Binary Search；但本題包含動態插入與刪除，平衡樹更合適。

---

（2）求下一個字典序排列

核心觀念

對排列 $A[0\ldots n-1]$ 求下一個字典序排列，標準方法如下：

1. 從右向左找第一個滿足

   $$A[i]<A[i+1]$$

   的位置 $i$，稱為 pivot。

2. 從右向左找第一個滿足

   $$A[j]>A[i]$$

   的位置 $j$。

3. 交換 $A[i]$ 與 $A[j]$。

4. 將 $i+1$ 到 $n-1$ 的部分反轉。

若找不到 pivot，代表目前排列是最大字典序，下一個排列為最小排列，也就是整個序列反轉。

---

給定序列

$$N=[9,8,7,6,5,4,3,2,1,0]$$

此序列由大到小排列，已經是所有排列中的最大字典序。

因此找不到任何 $i$ 使得：

$$N[i]<N[i+1]$$

將整個序列反轉：

$$[9,8,7,6,5,4,3,2,1,0] \longrightarrow [0,1,2,3,4,5,6,7,8,9]$$

所以其下一個字典序排列為：

$$\boxed{[0,1,2,3,4,5,6,7,8,9]}$$

---

關鍵程式碼

nextPermutation(A):
    n = length(A)
    i = n - 2

    while i >= 0 and A[i] >= A[i + 1]:
        i = i - 1

    if i < 0:
        reverse(A, 0, n - 1)
        return

    j = n - 1
    while A[j] <= A[i]:
        j = j - 1

    swap(A[i], A[j])
    reverse(A, i + 1, n - 1)

---

為什麼反轉 suffix？

找到 pivot 後，尾端區間 $A[i+1\ldots n-1]$ 原本是非遞增排列。交換 pivot 後，要使結果比原排列大且增加幅度最小，就必須將尾端改成最小字典序。

非遞增區間的最小排列就是反轉後的非遞減排列，因此可以用反轉完成。

---

正確性說明

• 由右向左找 pivot，表示盡量保留較長的字尾。
• 選擇最右側且大於 pivot 的元素，可讓增加幅度最小。
• 將 suffix 排成遞增，確保 suffix 是能形成的最小字典序。

因此所得結果正好是下一個字典序排列。

---

複雜度分析

最多掃描整個陣列數次：

$$T(n)=O(n)$$

使用原地交換與反轉：

$$S(n)=O(1)$$

即使 $n=10^5$，仍可在線性時間內完成。

解題技巧

看到「next lexicographic permutation」時，直接記住：

$$\text{找 pivot}\rightarrow\text{找右側較大值}\rightarrow\text{交換}\rightarrow\text{反轉尾端}$$

若整個序列為非遞增排列，答案就是整個序列反轉。

---

（3）AVL Tree 插入與再平衡

核心觀念

AVL 樹對每個節點定義平衡因子：

$$BF(v)=height(v.left)-height(v.right)$$

合法 AVL 樹必須滿足：

$$BF(v)\in\{-1,0,1\}$$

若出現 $BF=2$ 或 $BF=-2$，便需要旋轉。

---

逐步插入

插入 50

50

平衡因子：

$$BF(50)=0$$

不需旋轉。

---

插入 20

   50
  /
20

$$BF(50)=1$$

仍然平衡。

---

插入 60

核心觀念

本題考查四種能力：

1. 浮點數的正規化、符號位元、偏移指數與尾數表示。
2. 固定位元數造成的表示範圍限制與溢位。
3. 固定小數點加法與二補數運算。
4. 浮點數轉固定點數的演算法，以及兩者在精確度、範圍與應用上的取捨。

浮點數通常表示為

$$(-1)^s \times 1.f \times 2^e$$

其中 $s$ 為符號位元，$f$ 為尾數小數部分，$e$ 為實際指數。

Excess-15 編碼的關係為

$$E=e+15$$

其中 $E$ 是儲存在指數欄位中的值。

---

解題方法

（1）以 16 位元浮點格式表示 $-45.75$

步驟一：轉換成二進位

整數部分：

$$45_{10}=101101_2$$

小數部分：

$$0.75_{10}=0.11_2$$

因此

$$45.75_{10}=101101.11_2$$

步驟二：正規化

將二進位小數點左移五位：

$$101101.11_2=1.0110111_2\times 2^5$$

所以：

• 符號 $s=1$，因為數值為負。
• 實際指數 $e=5$。
• 尾數為 $1.0110111_2$。

步驟三：計算 Excess-15 指數

$$E=e+15=5+15=20$$ $$20_{10}=10100_2$$

步驟四：填入 10 位元尾數

題目指定 10 位元尾數包含隱含的 leading 1，因此將

$$1.0110111_2$$

補足為 10 位元：

$$1011011100_2$$

其中最後的 0 為補位。

因此 16 位元格式為：

$$\boxed{1\ |\ 10100\ |\ 1011011100}$$

也就是

$$\boxed{1101001011011100_2}$$

溢位處理

若將很大的正數與 $-45.75$ 相加，首先會將兩數的指數對齊。當大數的指數遠大於 $5$ 時，$-45.75$ 的尾數必須向右移動許多位，最後可能完全落在可保留精度之外，因此結果會近似於大數本身。

若相加後的實際指數大於此格式可表示的最大指數，便會發生浮點溢位。系統常見的處理方式為：

• 使用 IEEE 754 類似規格時，結果設為正無限大或負無限大。
• 沒有無限大設計時，飽和至最大可表示值。
• 設定溢位旗標，通知處理器或程式進行例外處理。

本題未指定特殊值編碼，因此重點是：指數欄位無法容納結果的實際指數時，產生 overflow；若未超過範圍，則大數會使 $-45.75$ 因精度不足而被捨去。

---

（2）以 ssss.ffff 固定小數格式相加

格式限制

ssss.ffff 僅有：

• 小數點左側 4 位元。
• 小數點右側 4 位元。

若採用一般 4 位元整數欄位，$45.75$ 的二進位形式為：

$$45.75_{10}=101101.11_2$$

它需要小數點左側 6 個位元，無法直接放入 ssss.ffff。

若 ssss 是 4 位元二補數整數欄位，可表示的數值範圍更小，通常為：

$$-8 \leq x \leq 7.9375$$

因此 $45.75$ 與 $-45.75$ 都無法在嚴格的 ssss.ffff 格式中表示。題目資訊不足之處在於未說明是否允許運算前先擴大整數欄位。

合理假設下的運算

假設保留 4 位小數位元，並將整數欄位擴大至足以容納 $45.75$ 的寬度，則：

$$45.75_{10}=101101.1100_2$$

負數使用二補數表示。使用足夠寬度後：

$$-45.75_{10}=-101101.1100_2$$

相加：

$$\begin{aligned} &101101.1100_2\\ +&(-101101.1100_2)\\ =&000000.0000_2 \end{aligned}$$

所以結果為：

$$\boxed{0.0000_2}$$

十進位結果為：

$$\boxed{0_{10}}$$

需要注意，若嚴格要求結果也必須寫成 4 位整數欄位加 4 位小數欄位，則可寫成：

$$\boxed{0000.0000_2=0_{10}}$$

但兩個輸入操作數本身已超出 ssss.ffff 的表示範圍。

---

（3）16 位元浮點數轉固定點表示法

假設目標固定點格式具有 $F$ 個小數位元，總寬度為 $W$，並採用二補數表示負數。

演算法步驟

1. 讀取 16 位元浮點數。
2. 分離：
   • 1 位元符號 $s$。
   • 5 位元指數欄位 $E$。
   • 10 位元尾數欄位 $M$。
3. 計算實際指數：

$$e=E-15$$

4. 還原實際數值：

$$x=(-1)^s\times M\times 2^e$$

其中 $M$ 表示包含 leading 1 的正規化尾數。例如尾數位元為 1011011100 時：

$$M=1.011011100_2$$

5. 將浮點數縮放為固定點整數：

$$X=x\times 2^F$$

6. 若 $X$ 不是整數，依需求採用截斷、四捨五入或銀行家捨入。
7. 檢查 $X$ 是否超出 $W$ 位元二補數範圍：

核心觀念

本題涵蓋三項重點：

1. 使用 Karnaugh map 化簡四變數 Boolean expression，並利用 don’t-care terms 擴大分組。
2. 使用 XOR、XNOR 與 majority function 設計邏輯電路。
3. 以「最長閘級路徑」分析 propagation delay：

$$\text{Delay}=(\text{最長路徑上的閘數})\times(\text{單一閘延遲})$$

以下假設所有閘皆為二輸入閘，且 XOR、XNOR、AND、OR 均視為一個邏輯閘，每個閘的延遲為 $10\text{ ns}$。

---

(1) 使用 Karnaugh map 化簡 $F(A,B,C,D)$

題目給定：

$$F(A,B,C,D)=\sum m(0,1,2,5,8,9,10,15)+\sum d(3,7,11)$$

其中：

• $1$：必須輸出的 minterm
• $d$：don’t-care，可視為 $0$ 或 $1$
• 未列出的 minterm：視為 $0$

採用列變數 $AB$、欄變數 $CD$，並依 Gray code 排列：

$AB\backslash CD$	$00$	$01$	$11$	$10$
$00$	1	1	$d$	1
$01$	0	1	$d$	0
$11$	0	0	1	0
$10$	1	1	$d$	1

第一組：化簡為 $\overline{B}$

將 $AB=00$ 與 $AB=10$ 的兩列全部圈成一組，共 $8$ 格：

$$m(0,1,2,3,8,9,10,11)$$

在此群組中，$A$、$C$、$D$ 都會變化，只有 $B=0$ 固定，因此得到：

$$\overline{B}$$

第二組：化簡為 $\overline{A}D$

將 $m(1,3,5,7)$ 圈成一組：

$$m(1,3,5,7)$$

此群組中：

• $A=0$ 固定
• $D=1$ 固定
• $B$、$C$ 變化

因此得到：

$$\overline{A}D$$

其中 $m(3)$、$m(7)$ 是 don’t-care，可用來擴大群組。

第三組：化簡為 $CD$

將 $m(3,7,11,15)$ 圈成一組：

$$m(3,7,11,15)$$

此群組中：

• $C=1$ 固定
• $D=1$ 固定
• $A$、$B$ 變化

因此得到：

$$CD$$

化簡結果

將三個群組相加：

$$\boxed{F=\overline{B}+\overline{A}D+CD}$$

此式已涵蓋所有指定的 $1$ minterms，且沒有涵蓋任何指定為 $0$ 的 minterm。

---

(2) 設計兩個輸出 $Y_1$、$Y_2$

$Y_1$：輸入中 $1$ 的數量為偶數

三個輸入中，$1$ 的數量為偶數的情況包括：

• $000$：有 $0$ 個 $1$
• $011$：有 $2$ 個 $1$
• $101$：有 $2$ 個 $1$
• $110$：有 $2$ 個 $1$

因此：

$$Y_1=\overline{A}\,\overline{B}\,\overline{C} +\overline{A}BC +A\overline{B}C +AB\overline{C}$$

此功能也可使用 XOR 表示。三個輸入的 XOR 在 $1$ 的數量為奇數時輸出 $1$，所以偶數同位元輸出為其反相：

$$\boxed{Y_1=\overline{A\oplus B\oplus C}}$$

也可寫成：

$$Y_1=(A\oplus B)\ \text{XNOR}\ C$$

$Y_2$：輸入中至少有兩個 $1$

符合條件的輸入為：

• $011$
• $101$
• $110$
• $111$

因此可由三個兩兩相乘項表示：

$$\boxed{Y_2=AB+AC+BC}$$

理由如下：

圖中確認第 5 題題幹為：「This question evaluates your understanding of cryptographic principles, algorithm design, and the implications of modern threats to encryption. (20%)」，第 5-(1) 題內容為：「Design a key distribution protocol that ensures secure communication between two parties. Your protocol must prevent man-in-the-middle attacks and minimize the number of communication rounds required. (5%)」。以下依題意作答。

---

核心觀念

本題考的是**金鑰分配協定（Key Distribution Protocol）**的設計，核心涉及：

1. Diffie-Hellman 金鑰交換（DH Key Exchange）：兩方在不安全通道上協商出共享秘密。
2. 中間人攻擊（Man-in-the-Middle Attack, MITM）的防禦：原始 DH 協定無法抵禦 MITM，必須結合公鑰認證機制（如憑證或已知可信公鑰）來綁定身份。
3. 通訊回合數最小化：以一回合（one round-trip, 1-RTT）的並行交換完成金鑰推導，後續受保護訊息的成功驗證才構成明確金鑰確認（Explicit Key Confirmation）。

關鍵數學基礎為離散對數問題下的 DH 公式：

$$Y^x = X^y = g^{xy} \pmod{p}$$

其中 $g$ 為生成元，$p$ 為大質數，$X = g^x$，$Y = g^y$ 分別為雙方公鑰。

---

解題方法

一、系統假設與參數設定

• 公開參數：大質數 $p$ 與生成元 $g$（亦可改用橢圓曲線群）。
• Alice 持有長期私鑰 $a$，對應公鑰 $A = g^a \pmod{p}$。
• Bob 持有長期私鑰 $b$，對應公鑰 $B = g^b \pmod{p}$。
• 可信公鑰假設：雙方已透過可信管道（如 CA 憑證、預先交換或 TOFU 機制）取得對方的正確公鑰，確保公鑰與身份的綁定。此假設是抵禦 MITM 的根本保障。

二、協定流程（1-RTT 並行交換）

Round 1（唯一一回合）—— Alice 與 Bob 同時（並行）執行：

方向	傳送內容
Alice → Bob	臨時公鑰 $X = g^x \pmod{p}$（$x$ 為 Alice 隨機選取的臨時私鑰）
Bob → Alice	臨時公鑰 $Y = g^y \pmod{p}$（$y$ 為 Bob 隨機選取的臨時私鑰）

雙方亦可在此訊息中附上對臨時公鑰的數位簽章（以長期私鑰簽署），即 Alice 附上 $\text{Sig}_a(X)$，Bob 附上 $\text{Sig}_b(Y)$，收方以已知可信公鑰驗章。

金鑰推導：

收到對方臨時公鑰後，各自計算共享秘密：

$$\text{Alice 計算：} K = Y^x = g^{xy} \pmod{p}$$ $$\text{Bob 計算：} K = X^y = g^{xy} \pmod{p}$$

核心觀念

RSA 加密與解密分別使用：

$$C \equiv M^e \pmod n,\qquad M' \equiv C^d \pmod n$$

其中明文整數必須滿足 $0\le M<n$。公鑰指數 $e$ 與私鑰指數 $d$ 通常滿足 $ed\equiv 1\pmod{\varphi(n)}$，因此在符合條件時，解密可還原原明文的模 $n$ 餘數。

解題方法

原卷圖列出的參數是明文 $M=12345$、公鑰指數 $e=17$、私鑰指數 $d=2753$、模數 $n=3233$。先檢查明文範圍：$12345>3233$，所以這個明文整數不符合 RSA 單一區塊的輸入條件；直接計算時，實際參與模指數運算的是 $12345\bmod 3233=2646$。

計算密文：

$$12345 \equiv 2646 \pmod{3233}$$

因為 $17=16+1$，逐次平方求模：

$$\begin{aligned} 2646^2 &\equiv 1871 \pmod{3233}\\ 2646^4 &\equiv 2535 \pmod{3233}\\ 2646^8 &\equiv 2254 \pmod{3233}\\ 2646^{16} &\equiv 1473 \pmod{3233} \end{aligned}$$

因此：

核心觀念

題目考查 RSA 與對稱式加密在計算成本上的差異。RSA 加密使用公開金鑰 $(e,n)$，將訊息區塊 $M$ 加密為

$$C \equiv M^e \pmod n$$

AES 則使用共享的對稱金鑰處理資料。比較時要同時看運算量、每次運算的成本，以及傳輸大量資料時的整體效率。

解題方法

圖中第 (3) 題要求分析 RSA 加密的計算複雜度，並比較其與 AES 在大量資料傳輸時的效能；同頁第 (2) 題另列有 $e=17$、$d=2753$、$n=3233$，那是前一小題的加解密參數，不影響本題的複雜度比較。

RSA 加密的主要運算是模指數 $M^e \bmod n$。用平方乘法計算時，約需 $O(\log e)$ 次模乘，因此若將一次模乘視為基本運算，RSA 加密的運算量為 $O(\log e)$ 次模乘。若進一步考慮大整數運算，令模數 $n$ 有 $k$ 位元，一次乘法成本記為 $M(k)$，則複雜度約為

$$O\bigl(M(k)\log e\bigr)$$

常見情況下，公開指數 $e$ 選得較小，例如 $65537$，可減少模乘次數；但每次模乘仍涉及大整數運算。

核心觀念

量子運算對 RSA 的威脅，來自 Shor 演算法能在足夠大型且具容錯能力的量子電腦上，有效率地分解大整數。RSA 的公開金鑰包含 $n=pq$ 與公開指數 $e$；若攻擊者分解出 $p,q$，便能計算 $\varphi(n)=(p-1)(q-1)$，再由 $d\equiv e^{-1}\pmod{\varphi(n)}$ 求出私密指數 $d$，進而解密資料。

格基密碼的安全性則建立在格上困難問題之上，例如帶誤差學習（LWE）問題。這類問題在適當參數下，沒有已知的有效量子演算法可解。

解題方法

圖中第 5-(4) 題要求說明量子運算對 RSA 的威脅，並概述一種抗量子加密演算法，並以格基密碼為例。作答時先連結 RSA 安全性與整數分解，再說明格基加密如何利用小誤差構造公開金鑰，讓持有私鑰者消去主要項並還原訊息。

以簡化的 LWE 公開金鑰加密為例，令 $A\in\mathbb{Z}_q^{n\times m}$，選取私鑰向量 $s\in\mathbb{Z}_q^n$ 與小誤差向量 $e\in\mathbb{Z}_q^m$，計算：

$$t=A^Ts+e\pmod q$$