2018q1 Homework3 (list)

tags: shaimejump520

contributed by <shaimejump520>

作業說明連結 D05: list

預期目標

• 嘗試研讀大型軟體專案
• 學習 Linux 核心原始程式碼的資料結構
• 資料封裝和 C 語言程式設計技巧
• 複習機率統計，及早脫離鄉民口中的「文組^TM」
• 兼顧理論和實務

作業要求

• 回答上述「生日悖論」、「Linux 風格的 linked list」，和「針對 linked list 的排序演算法」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
• 在 GitHub 上 fork linux-list，參考 examples/insert-sort.c 和 examples/quick-sort.c 的實作方式，實作 merge sort，並且在 tests/ 目錄提供新的 unit test
• 研讀「你所不知道的 C 語言」的 函式呼叫篇 和 技巧篇 探討 linux-list 的 include/list.h 的實作考量 (在上述檢查清單已提及部分)
• 承上，實作測試程式，批次建立包含若干大小的 linked list，隨機放入數值為介於 1 到 366 之間 (包含) 的節點 (代表 day number) ，至少應該涵蓋 10¹, 10², 10³, … 10⁶ 等數量，透過前述的 insert, quick, merge sort 進行排序，分析執行時間並解讀其行為
  • 需要有檢驗的程式碼
• 承上，設計 deduplication 程式，將上述輸入中的數值挑出重複的節點並與刪除，透過統計分析，解讀執行時間分佈，以及探討 data deduplication 的效益
  • 比照生日悖論，提出統計模型和數學分析
  • 參照 Remove duplicates from a sorted linked list
• 延續 A Comparative Study Of Linked List Sorting Algorithms 的方式，量化分析上述步驟，並且提出效能改善機制
• 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「作業區」

生日悖論

如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式

• 要解決這個問題，首先要先學會 LaTeX 語法，我第一次作業偷懶沒有先學抱歉QQ，終於碰到了阿…，先看個 LaTeX 語法與示範壓壓驚
• 在排版時覺得原本使用的\dfrac和\frac放在指數時看起來十分不理想，基於強迫症就去查到了\tfrac這種格式，可以讓分數放在指數時大小適中又美觀XD

$$\begin{gathered} byTaylorseries:e^x=1+x+{\displaystyle \frac{x^2}{2!}}+... \\ withsmallx,wecanassumethatx<<1,thus:e^x\approx 1+x \\ andweget:e^{-\frac{1}{365}}\approx 1-{\displaystyle \frac{1}{365}} \\ P(n)=1-\overline{P}(n) \\ \begin{array}{rl}\overline{P}(n)& ={\displaystyle \frac{364}{365}}\times {\displaystyle \frac{363}{365}}\times ...\times {\displaystyle \frac{365-(n-1)}{365}}\\ & =(1-{\displaystyle \frac{1}{365}})\times (1-{\displaystyle \frac{2}{365}})\times ...\times (1-{\displaystyle \frac{n-1}{365}})\\ & \approx e^{-\frac{1}{365}}\times e^{-\frac{2}{365}}\times ...\times e^{-\frac{n-1}{365}}\\ & =e^{-\frac{1+2+...+(n-1)}{365}}\\ & =e^{-\frac{n(n-1)/2}{365}}\\ & =e^{-\frac{n(n-1)}{730}}\end{array} \\ P(n)=1-\overline{P}(n)\approx 1-e^{-\frac{n(n-1)}{730}}\approx 1-e^{-\frac{n^2}{730}} \end{gathered}$$

Birthday problem 對資訊安全的影響在哪些層面？

• 先研讀 bitrhday attack，得知這是一種基於 birthday problem 理論產生的 brute-force attack，由於對於資料做加密傳輸的方式，多數是使用 hash function 產生加密過後的資料做傳輸，而 birthday problem 的特性，只要嘗試
  $2^{n/2}$ 組輸入，便有很高的機率能早到與原明文相同的 hash value，從而能夠接收者不知情的其況下竄改訊息、達到攻擊的目的

參考 LinYunWen的共筆 中提供的 reference:雜湊 蠻易懂的
但我的疑問是，為何一個路人攔截訊息，能夠確定你加密的 hash function 是哪一個而能夠以此完成攻擊呢？

• 另一種問題 – 合約詐欺，這是在知道 hash function 的情況下，可以找到與一份100萬合約具有相同 hash value 的1000萬合約，誘騙對方簽署

• 所以常見的解決方法是加長 hash value 的 bits 數，如此一來增加了找到相同 hash value 訊息的難度，從而化解 birthday attack 然而相對的，加長資料長度後必定會帶來運算更加複雜、效率也因此更差

像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？

參考資料

• LaTeX 語法與示範