第八學期修課心得

Eighth semester

已經是最後一個學期了。雖然一兩個禮拜前學期的最後一堂課就結束了但一直沒有提筆開寫。
感覺沒什麼臉寫修課心得但還是想有始有終。

日文二下

本學期理論上唯一(?)可能讓我畢不了業的課(如果被當的話)。
從藍色那本課本變成綠色了。沒有修到日文三讓人感覺這課本只用一學期很浪費。
不得不說感覺進度真的好緩慢。兩次段考各考三課,感覺範圍小到填空能填錯的選項也沒多少個。
以這學期來說的話,感覺我得到的價值是把可能形、意向形還有「〜てきます」「〜ていきます」「〜ておきます」這些文法在課中系統性的學了一遍。還有就是每個禮拜可以跟坐前面的同學練習講日文。

本學期的最後還有一個在 NTU COOL 上做的 N4 模擬測驗。不知道是版權還是怎麼樣的還需要老師給密碼才能參加。反正不算分而且 N3 都過了就沒管這個測驗做得怎麼樣(?)

高等資料結構

卡恩開的一門不知道之後會不會再開的課。帶著憧憬(?)來修。

每次作業大致上分成兩部份,Part I 是證明題,Part II 則可以選擇要做 Benchmark 還是 Paper Reading。Benchmark 是針對選定的課題寫程式 Benchmark,而 Paper Reading 是從論文清單裡面挑出來 summarize 以及提「有用的問題」。

期初的時候小看了 HW1,最後一個禮拜才開始看,Part I 四題裡面兩題都跑去看了提示。一題是題敘裡面說存在一篇 CF 文章,放棄自尊心跑去 google 就可以找到了,一題是讀懂題敘有 reference 的原論文,並想辦法弄簡單一點(原論文是樹但這題是鏈)。死線是週一的中午十二點,但因為後量子密碼學是週一早上,所以我是把死線當作星期天 23:59。Part I 拖到了週六晚上才寫完,六晚+日早讀了幾篇論文之後發現好像一天做不完 paper reading 就跳槽到 benchmark。意外的覺得老師建議的框架 Google Benchmark 很好上手,因為會產出完整的 json 檔描述 benchmark 每個 task 的時間之類的,我就丟給 GPT 生一個生圖表的 python script(再自己改一下),總之寫一下觀察拼湊出一個報告。做的時間非常少,但我覺得看上去的完成度應該很不錯。

接著 HW2 馬上又來了。雖然老師一直宣稱這比 HW1 還要簡單,但我怎麼看都是比 HW1 難。
一題 split tree 我根本找不到有誰好好證明過,都是在說明概念(我覺得我找到 這個影片的最後五分鐘 有講已經蠻神奇的了但還是好難看懂)。
另一題要證 wilber-1 bound 的反例,雖然好像原則上解答應該要約是一頁 A4 紙,但我真的想不到怎麼把原本論文裡面有大概十頁在證的東西弱化或怎樣之後塞進一頁。感覺不是給人寫的。想辦法模仿論文改寫成自己的話,寫了十個 lemma 跟 theorem 都還證不完。證的還是已經弱化的版本。
HW2 一樣不會讀 paper 選了 benchmark,但因為 Part I 那題耗費太多心力(?)感覺這次的完成度不太高,就只是做完 benchmark 的題目敘述裡面的最低要求而已。

本來接下來應該會出現 HW3 的,但老師說他自己嘗試寫之後發現證不出來(?)之類的,讓我們苟且偷生了好幾個禮拜(?)接下來的 HW4 就變成了最後的作業。很明顯我並沒有吸取前車之鑑,寫作業的流程和 HW1 完全同構,只差在這次 benchmark 的東西是我第一次學的 HyperLogLog,想不到有什麼有趣的 payload 或是實做細節可以觀察。

上課的進度跟作業的數量一樣跟期初的規劃都不太一樣,有不少堂原本規劃一週的東西講了兩週左右。剛開始上課的感覺有不少是花了很多時間鋪陳很簡單的東西,然後突然就像飆車一樣講完很難的部份,不過感覺後半有正常一點(整堂平均都很難)

做完 HW4 好像就該開始做 final project 了,但我真的不知道該怎麼開始做。
final project 一樣有兩種方向,一種是「寫有用的程式」,另一種則是「分享新的研究想法、證明」。

引用自 MIT 6.851 期末報告說明:“Solved problems are not candidates for projects. But if you have ideas for other types of projects, feel free to ask staff about suitability.”

因為上面這段話,我覺得我們沒辦法在期末報告前想到新的東西,所以我們組最後變成跑去寫程式了。討論選定的主題是 Yao’s algorithm(解最小生成樹),然後做出來一個感覺跟一次作業的 benchmark 差不多只是大了一點的東西。我們也有做 visualization 不過那部份有點陽春。
一個小趣事是報告的時候老師問「Walk through yao 的 yao 要大寫嗎?」我想說「噢,要」(Yao: 要)
期末報告的時候看到好像不少組其實就是報 paper,不知道這樣算不算有達成要求(我也不知道我們這組這樣應該算達成幾分的要求 QQ)。

雖然作業成績的細項都還沒看到,但我猜我應該只有 HW1 Part II 是有拿到 A+(我覺得那個真的看起來美侖美奐,如果我沒有在這篇部落格說可能都不會想到那是一個下午做出來的),最後拿到的成績是 A。

後量子密碼學

看著量子這兩個字就讓人想選的課名。同一時間還有鄭皓中教授開的量子資訊與計算,兩個衝堂只能選一個。因為我想說我高三有去過量子資訊與計算了(雖然我最後停修了QQ)就先選了後量子。

意外的是一門幾乎每週點名的課,不過我覺得這門課的資訊密度應該不會想要讓人漏掉課(而且我這學期選超少課)

教授表示他原本是打算在這學期就要停開這門課,但因為一些像是行政失誤的問題就繼續開了。感覺課程本身像是兩條路線揉合而成的,一條路線是「後量子加密的科普」,另一條路線是「怎麼快速做多項式乘法」。
前者的話,首先會講一些比較一般性的有關後量子的知識,然後會介紹特定的後量子密碼學的演算法,例如 code-based 的 McEliece、lattice-based 的 NTRU 等等。有幾次是 guest lecture 的形式,由外國的講師介紹(講英文)。
後者則是佔了期中考大部分的內容,包含了 Barret Reduction、Montgomery Multiplication、Karatsuba、Toom-Cook、NTT(Number theoretic transform)等等。

後量子的加密方法是介紹的蠻詳細的,但沒辦法真的證明安全性讓我我心裡總覺得癢癢的,大概是因為還沒有人類知道 P 等不等於 NP,或者我沒有修密碼學的理論基礎。

快速做多項式乘法的部份,雖然感覺學過的東西很多(比如 Montgomery 我應該之前有一篇 CTF 文章剛好查到有用到),不過經由這門課也學到了更多的細節(例如 mulhi 的存在,以及原來只要 $a\cdot b < R \cdot M$ Montgomery 的 redc(a, b) 算出來就會對)。
講課的時候常常在講一個演算法之前鋪陳很長,像一個可以放進 Veritasium 的故事;也常常會不知道為什麼就偏題跑去講別的故事。然後進度安排跟高等資料結構一樣怪。前一週還在講前置作業,例如介紹費馬小定理(?),然後下一週就馬上用一個早上從零開始講完 NTT。甚至有一堂課是直接一個早上從零開始介紹量子演算法最後講 Shor’s 跟 Grover’s algorithm。沒有先聽過根本聽不懂的溺水式趕火車教學法(?)不知道其他人吸收得怎麼樣。另外因為老師的專長(和他發的一些論文)好像是對這些用到多項式的密碼學壓常,所以常常會發生才剛介紹一個演算法就聽到老師說怎樣實做會比較快(aka 壓常),是有新知識但我會覺得節奏很奇怪。

期中考是開電腦考,但不能使用網路(忘記有沒有說禁止本地 LLM)。考前準備是把所有投影片都下載下來並瀏覽過什麼東西在哪裡。考了個 118/120(炫耀),雖然是六題裡面取最好的四題,但我幾乎寫了五題。證明題跟問答題作文力還是有的。跟往年的題目一樣都會出現一些奇怪的問題,例如

  1. 想要求 X^-1 mod B^n 時經常使用 Hensel lifting (共 40 分)
    a. 解釋何為 Hensel Lifting, 並說明它和 Newton’s Method 的關係 (10分)
    b. 試求 4591^-1 mod 10000 (5分)
    c. 試求 4591^-1 mod 65536, 其中 65536 = 2^16 (10分)
    d. 有環 R = Z_256[x]/(x^5-1), 即 Z[x] mod 256 mod (x^5-1),
    試在 R 中求 (x^3+x^2+1)^-1 (15分)
    e. 承上, 為什麼這題不是求 (x^2+1)^-1 或 (x^3+2x+1)^-1 ? (10分)

(因為我懶得找所以上面是從 ptt 抓來的考古題)這裡的 1.e 感覺回答的方向非常的發散,感覺像是要讀出題者的心一樣(?)不過平常上課老師也常常這樣突然問一些很發散的問題所以應該算是他的 style。

期初就有預告要做寫程式拼壓常的 final project,不過細節直到期中考考完才知道。
總之是要寫一個程式做 $N$-bit 的大整數乘法,目標是打贏 GMP 的 mpz_mul,至於要選多大的 $N$ 是自己決定,另外平台是發給我們每個人測的 Raspberry Pi 4,架構是學期當中一直提到的 ARM NEON(跟 online judge 常見的 x86 不一樣)。
final project 的 github repo報告的 slide 都是公開的所以我就不再寫一次了。大概花了整整兩個禮拜搞這個東西,看到其他人做的之後會覺得我是不是用力過猛了(X
老師是說只有我是他想像中的作法,他表示可能他定的題目的方向太發散了(?)我看到其他人的作法之後反而覺得自己像是腦筋正攻XD 反正壓得也很有成就感。期末報告結束後因為剛好下午要趕去聚餐就急著離開了,有點「明明應該是感傷的大學最後一堂課但卻弄得我好像很急著離開一樣」的複雜心情。因為 final project 做得好的優越感(?)讓我印象還不錯,不知道以後會不會再開。

Misc

日K

學期結束後不知道為什麼被一群比我大兩屆以上的人揪去日K。大家都好會唱。不知道為什麼拿了三隻麥克風但一首歌都是一個人唱(各自獨秀)。最後一首歌《再会》是眼皮點的,但他問說其他會唱的要不要拿麥起來唱,然後就是一個超會唱的人(眼皮)和超不會唱的人(我)的合唱。尷尬程度和之前選訓營時 balbit 跟 utaha 揪 jstris 的時候我說要加有的比(?)
反正我應該努力點滿四個小時的七分之一了,臉皮厚一點也不是壞事,也是有唱得還可以的歌(至少我自己覺得 ODDS & ENDS 應該可以)。

k033 project

期初跟 casperwang 他們去嘗試做一個量化交易 project(?)不過到了學期中因為比較忙也就沒有參加。感覺在項目剛開始的時候我有點大放厥詞,結果最後要做事的時候都好懶。

NASA

最一開始這一年度會打算繼續做 NASA 應該是因為感覺更前面那一年我在 NASA 都沒做什麼事的罪惡感。
今年做起來的感覺是感覺開始上手也開始麻木了,基本上目標是就被動的「讓工作站活著」,然後也很被動的去開月會跟週會。
我自己的感覺是 NASA 也是一個好多和尚沒水喝的地方。月會簡報跟週會簡報都不知道應該要誰做,好幾次都感覺是我怕真的沒人做簡報跑去做,像膽小鬼賽局一樣。學期的後來我有幾次特意講自己不會去月會或週會然後說好聽一點是傳承說難聽一點感覺像在踢皮球(
不過我也膽小(或懶惰)而沒有去當一階的 TA 所以搞不好也沒什麼資格講人(?)
領 NASA 的薪水感覺也很可怕,都像是讓我以後不能選市長的黑歷史。(我沒有要選市長)

畢業典禮

看到很多平常不會看到的人,拍了幾張照。
唯一想吐槽的東西是最後的拋帽子環節根本是學士帽大風吹,都不知道最後撿了誰的帽子。
結束之後跟著一起來的阿公阿嬤去吃飯,阿公請客(?)

結語

畢業的心得是:
悲報!ワイ!ニート!

打完才發現從開始寫心得到現在已經過了一兩個禮拜,好會拖。之後想寫幾篇文章來寫後量子密碼學教的東西,Montgomery 跟後量子那些的。也可以順便推廣一些東西像是 qcoder.jp 或是遊戲(?)

comments powered by Disqus