網頁

Tuesday 23 April 2013

KTH Exchange 45: 理想與現實

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

今次的題目有求 ae 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
這個倒是挺有趣的, 完全沒有想過這個問題
所以我決定稱這份功課為「理想與現實」

Sunday 21 April 2013

KTH Exchange 44: 四月,春天

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


殘留的積雪

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





這才是四季分明

Thursday 11 April 2013

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