KTH Exchange 47: Stockholm city revisit

這個星期完 sem, 回 KTH 只是做 presentation 和上最後一堂

夏天的 Stockholm 和冬天的景色截然不同, 可以說是到了兩個地方
雖然已經強調了很多次這裏才是真正的四季分明, 而且春天又和秋天不同
只剩下一個半月就離開 Stockholm, 於是在市中心懷舊一下

首先是一開始暫住 hostel 時, 到 KTH 所經之路:

八月時暫住的 hostel, 已是九個月前的事:

市中心:

據聞這裏一個星期多前是櫻花, 不過來遲了

比較起來, 還是冬天有趣一點

KTH Exchange 46: 日不落

五月, 日光時間上升至 16 小時
但考慮到大氣層折射, 其實 Stockholm 是沒有一刻全黑的
從下圖可以看到, 五月至七月其間, 即使是凌晨也有日光

Figure from weatherspark

對比香港的:

Figure from weatherspark

下面這張相是在凌晨三時, 對著北面的天空拍:

由於房間向東, 原本的百葉簾隔光效果奇差, 不得不以黑色垃圾袋加強

KTH Exchange 45: 理想與現實

cryptography assignment, deadline 剛好在 KTH challenge 以及我出題的 Codeforces round 附近, 很多題目都沒有時間仔細想
與 lecture 不同, assignment 有不少是 practical 的題目
有些是要寫 program 交上 Kattis judge

今次的題目有求 a^e mod n, chinese remainder, 看下去很熟悉
不過 input size 是由 256 bit 起跳, multiple test case, 而且 time limit 只有 1 秒 !
要寫 bignum division 和 mod, 還要 optimize, 花了不少時間
最後一條是 given (N, e, d), factorize N
搞完一大輪後還是 TLE, 忍不住轉去用 Java BigInteger

然後功課還有「閱讀理解」題
如果有兩個 RSA modulus share prime factor, 只要求它們 gcd 可以輕鬆破解
雖然理論上 RSA 用的 modulus 應該是由 random 的 prime 相乘
但是現實中因為用的 randomness 有問題, 而會導致使用 same prime
這個倒是挺有趣的, 完全沒有想過這個問題
所以我決定稱這份功課為「理想與現實」

KTH Exchange 44: 四月，春天

連續兩星期好天氣, 日間氣溫上升至十位數字, 終於融掉大部份積雪
就像由黑白 mode 回到彩色 mode
也終於可以不戴帽, 手套出門
冰湖也開始融化

殘留的積雪

 隨著春天的到來, 出現的鳥類的多樣性也隨之上升

這才是四季分明

KTH Exchange 43

cryptography presentation, topic 4 揀 1, 12 mins
最後選了 garbled circuits
Alice 和 Bob 各自有 input X, Y, 可以在不洩漏自己 input 下共同 compute f(X, Y)
雖只是 passive adversary 的版本, 不過 construction很巧妙, 所以被吸引了
連帶睇埋 oblivious transfer
presentation rehearsal 了數次, 但到了 present 時仍然開始 overrun, 砍掉最後 1/3, 幸好那 part 砍掉也不影響主題, 沒有人發現

今天同時有 training, 其中一條 turns out 是問 DFA Equivalence
來自 313 的印象, 打算先做 DFA minimization 再 compare, 結果寫起來也有點長
結果做不完, 回家繼續揼, 最後搞了一大輪終於過掉
但其實原來 DFA Equivalence 有更簡單巧妙的做法, 而且接近 linear time!
詳看 Problem D