pyfactor

基于python的整數分解工具

介紹

pyfactor是一個完全使用python編寫的整數分解工具，最大可以分解十進制60位以內的RSA數n=pq。

這個工具是我的畢業設計作品，純粹是一個實驗性質的小程序，和目前程序的整數分解工具

(如：msieve，yafu等等)相比，運行效率很低。但其分解能力可以完全勝任教學目的

支持的python版本：3.5以上

依賴的庫：SymPy(推薦版本為1.3以上)

建議直接安裝Python科學計算的發行版——Anaconda，默認就預裝了常見的python的科學計算庫。

目前只提供了核心算法包pyfactor、命令行(CLI)工具pyfactor_cli.py。

圖形界面(GUI)工具pyfactor_gui.py正在開發中，使用python默認的GUI套件tkinter。

CLI版本只完成了一個粗糙的原型，而GUI版本可以單獨設置參數、調用具體的算法，

因此，推薦學弟學妹使用GUI版本

關于幫助文檔

在doc文件中的算法介紹其實是我畢業論文中的一個片段，可以幫助同學們理解pyfactor中使用的整數分解算法。

如果要深入了解某個算法，或者想要改進算法的話，推薦同學們閱讀參考文獻中列出的論文。

算法介紹

pyfactor使用了如下的整數分解算法

Pollard's rho (Brent改進方法)

Pollard's p+1

Williams p-1

ECM (橢圓曲線因子分解算法)

SIQS (二次篩法)

其中 p-1方法 和 p+1方法實現了原始論文的第一階段算法；

ECM方法目前還不穩定，找到十進制20位以下的素因子應該沒問題；

SIQS方法尋找光滑數仍然較慢，分解50位以下的整數應該沒問題；

使用說明

pyfactor依賴SymPy，使用前需要安裝SymPy

該工具的目標人群是學習整數分解算法的學弟學妹，對于較大的整數運行效率慢的話，請不要吐槽(逃……)

pyfactor目前提供了一個命令行(CLI)工具 —— pyfactor_cli.py，

在命令行下運行 pyfactor_cli.py，可以使用本工具。

圖形界面(GUI)工具 —— pyfactor_gui.py使用python tkinter開發，可以在界面中選擇單獨的算法。

如果想要單獨調用某個整數分解算法的話，可以直接調用pyfactor這個python包

pyfactor_cli 命令行工具

pyfactor_cli命令行工具依次使用試除法、brent方法、p+1方法、p-1方法和SIQS尋找素因子。

-h顯示幫助信息

-v顯示版本信息

--rho=nPollard's rho方法的迭代次數限制為 n 次

--pp1=BWilliams p+1方法的光滑界設置為 B

--pm1=BPollard's p-1方法的光滑界設置為 B

--ecm=dECM方法尋找的素因子大小限制為十進制 d 位

pyfactor_cli命令行工具目前不支持單獨使用某個整數分解算法，也不進行素性測試。

如果要單獨調用具體的分解算法，可以在python中直接導入相應的包，示范如下：

from pyfactor.rho import brent # 導入Brent方法(Pollard rho方法的改進版本)

from pyfactor.pm1 import pm1 # 導入Pollard p-1方法

from pyfactor.pp1 import pp1 # 導入Williams p+1方法

from pyfactor.ecm import parallel_ecm as ecm # 導入ECM方法

from pyfactor.siqs import siqs_main as siqs # 導入SIQS方法

>>> brent(2**2**5+1)

641

>>> pm1(12341234)

73

>>> pp1(123412345)

35

>>> ecm(2**2**7+1)

59649589127497217

>>> siqs(760525083515850218314740691253136455584879)

(845041919143549452517, 899985037767881262787)

前四個算法的輸出是輸入整數的一個非平凡因子，siqs的輸出是兩個非平凡因子。

具體細節可以直接看源代碼。要注意，這些算法不會對輸入參數進行檢驗，因此請確保輸入參數是合數。

SIQS算法的輸入參數要大于等于十進制30位。

pyfactor_gui 圖形界面工具

pyfactor_gui 是 pyfactor 的一個GUI接口，支持單獨選擇某個整數分解算法。

同時，pyfactor_gui還添加了素數生成與檢驗功能。

總結

以上是生活随笔為你收集整理的python整数分节输出_pyfactor的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。