Tag Archives: algorithm

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。 一般的 Bloom filter (BF) 會有這些問題: The inability to delete items Poor scaling out of RAM The inability to resize dynamically The … Continue reading

Posted in CDN, Computer, Murmuring, Network, Programming | Tagged , , , , , , , , , , , , , | Leave a comment

BitTorrent 對 SHA-1 的改善計畫?

最新一版的 Tails 不再支援透過 BitTorrent 下載,會被導去「Biterrant attack」這邊的連結,裡面有一些關於在 SHA-1 打穿後要怎麼判斷。 BitTorrent 的討論 (包括 BitTorrent 發明人 Bram Cohen 的參與) 則是在 GitHub 上:「Transitioning to stronger hash function · Issue #58 · bittorrent/bittorrent.org」,不過看起來連要用什麼 hash algorithm 的定案都還沒有啊... 而且二月底比較熱鬧一點,三月後都沒什麼動作了。 看起來短時間也不會有動作了...

Posted in Computer, Murmuring, Network, P2P, Security, Software | Tagged , , , , , , , , , , , , | 1 Comment

在面試時的資料結構與演算法的問題

在「500 Data structures and algorithms interview questions and their solutions」這邊看到在 Quora 上整理出來的題目 (以及解答)。 每個題目下面也都有地方可以留言,等久一點應該會更豐富? 另外一個不錯的地方在於題目的分類,舉例來說,如果想要練習 Backtracking,可以去翻對應的題目出來練。

Posted in Computer, Murmuring, Programming | Tagged , , , , , , | Leave a comment

Tim Berners-Lee 拿下 2016 年 Turing Award

今年的 Turing Award 頒給了 Tim Berners-Lee: For inventing the World Wide Web, the first web browser, and the fundamental protocols and algorithms allowing the Web to scale. 終於啊...

Posted in Browser, Computer, Murmuring, Network, Science, Software, WWW | Tagged , , , , , , , , , , | Leave a comment

Git 支援其他 Hash 演算法的進展

Git 用 SHA-1,而 SHA-1 又破的問題使得 Git 開始計畫其他 hash algorithm (「Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision」)。 在「"uchar [40]" to "struct object_id" conversion continues.」這邊可以看到一些動作,先把本來的 uchar[40] 換成一般性的 struct object_id。 Hacker News 上的「The beginning of Git supporting other hash algorithms」也有一些討論可以看。

Posted in Computer, Murmuring, Programming, Security, Software | Tagged , , , , | Leave a comment

NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。 類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key … Continue reading

Posted in Computer, Murmuring, Network, Security | Tagged , , , , , , , , , , , , , | Leave a comment

透過演算法修照片的工具

看到「A simple interface for editing natural photos with generative neural networks.」這個工具,直接看這個兩分鐘的影片比較清楚知道他想要做的事情: 當你修正了某一個點後,這個工具就透過演算法改變其他的點,讓照片看起來變得自然... 作者所發表的論文可以在「Neural Photo Editing with Introspective Adversarial Networks」這邊下載到。

Posted in Computer, Murmuring, Network, Photo, Programming, Recreation, Software | Tagged , , , , , , , | Leave a comment

Dropbox 儲存密碼的方式

記得 Dropbox 前陣子才強迫所有使用者重設密碼:「The Dropbox hack is real」,官方的報告在這:「Resetting passwords to keep your files safe」,當時洩漏出來的資訊可以知道 2012 年的時候 Dropbox 用的是 SHA1: What we've got here is two files with email address and bcrypt hashes then another two with email addresses and SHA1 hashes. … Continue reading

Posted in Cloud, Computer, Murmuring, Network, Programming, Security | Tagged , , , , , , , , , , , , | Leave a comment

Facebook 推出的 Zstandard 壓縮

Facebook 發了一篇出來,講 Zstandard:「Smaller and faster data compression with Zstandard」,可以看到: 如果與 Google 去年 open source 出來的 Brotli 相比,Zstandard 則是著重在速度,想要做出一個比 zlib 快很多但又比 zlib 壓的好的壓縮演算法。

Posted in Computer, Murmuring, Software | Tagged , , , , , , , , | Leave a comment

Facebook 推薦好友機制的演算法讓更多的隱私問題浮現...

在「Facebook recommended that this psychiatrist’s patients friend each other」這邊報導了 Facebook 推薦好友機制的演算法意外的拉出了奇怪的東西: [...], such as this story from Lisa*, a psychiatrist who is an infrequent Facebook user, mostly signing in to RSVP for events. Last summer, she noticed that the social … Continue reading

Posted in Computer, Murmuring, Network, Security, Social, VPN, WWW | Tagged , , , , , , , , | Leave a comment