Pollard's rho algorithm - LayerX Research

Pollard's rho algorithm

確率的アルゴリズムの素因数分解アルゴリズムとして有名なPollard's Rhoアルゴリズムを応用してECDLPに用いる。

related: SexTNFS / SURK-CMA

https://ja.wikipedia.org/wiki/ポラード・ロー素因数分解法

https://en.wikipedia.org/wiki/Pollard's_rho_algorithm_for_logarithms

https://mathtrain.jp/rhoalgorithm

http://orolog.hatenablog.jp/entry/20100804/1280943541

https://qiita.com/gushwell/items/561afde2e00bf3380c98

https://wacchoz.hatenablog.com/entry/2019/01/05/230128

http://shinshu.fm/MHz/14.30/archives/0000448516.html

http://idm.s9.xrea.com/factorization/rho.html

https://pdfs.semanticscholar.org/18e4/da0bbfb9f2f673567e6d72f3f53bc8dbc56c.pdf

http://iamkush.me/pollard-rho-with-the-brent-modification/

In Rust

https://github.com/phillip-h/reikna/blob/4799db1f9f432be8e220a37f26af0fef63a09020/src/factor.rs#L223-L296

フロイドの循環検出法

https://ja.wikipedia.org/wiki/フロイドの循環検出法

https://www.shookuro.com/entry/2018/08/11/120854

http://hidekazu.hatenablog.jp/entry/2016/04/01/204153

ミラー・ラビン素数判定法

https://ja.wikipedia.org/wiki/ミラー–ラビン素数判定法

https://qiita.com/zu_rin/items/25521b5870389e0f85bf

https://qiita.com/srtk86/items/609737d50c9ef5f5dc59

https://www.slideshare.net/DEGwer/ss-14119074