yafu质因数分解工具的笔记

yafu

简述

yafu 是数学爱好者们所写的一个关于大整数分解的项目，在现在的公钥加密方案中，大整数分解（质因数分解）十分重要，故 yafu 通常被用于快速分解大整数（例如分解 RSA 中的 n）。

yafu 的成功离不开其他开源代码，它使用目前来说最先进的自动化代码，在智能和自适应方法中结合分解算法，最小化分解时间。

同时需要注意的是，yafu 是纯命令行驱动的，可以使用交互输入模式。

安装

可以在 GitHub 主页上下载已经构建好的版本（或者是自行编译），也可以在 SourceForge 上下载已经打包好的版本（解压即可）。

仅需要对应的二进制即可运行（一般使用 x64 版本），但需要注意的是，yafu 所需的依赖文件是要与二进制文件在同一目录下的。

yafu 自身是通过支持库 msieve 运行分解算法的，但不支持特殊的 NFS 算法。

Number Field Sieve（NFS）安装

不需要理会该节，仅是 README 的必要翻译。

Number Field Sieve，数域筛法，是最快的、效率最高的（渐近意义下）整数分解方法，用于解决 IFP 和 DLP 问题。

想让 yafu 使用 NFS 算法进行质因数分解，可以直接在 https://sourceforge.net/projects/ggnfs/ 该网站中下载对应版本的 GGNFS 二进制文件的压缩包，再自解压到 yafu 所在目录（如 ./ggnfs-bin 下）。

随后在 yafu.ini 中填入 ggnfs_dir=./ggnfs-bin/（注意变量名不能冲突）。

yafu.ini

该文件是 yafu 运行的初始化文件。

需要注意，yafu 的 input_size 以十进制算。例如 1903387770 是 10 位数。

%%% 常规选项 %%%

% 多线程算法的指定线程数
threads=1

% 米勒-拉宾素性检验的证人(witnesses)数量
nprp=7

% 信息输出等级设为1，默认为0
v

% 关闭信息输出
silent

% 跳过启动时的时钟测试
no_clk_test

% 运行给定脚本
script="my_script"

% 指定会话日志(会话日志记录运行的命令，随机数种子，系统信息和一些启动项)
session="session.log"

% 使用给定文件名的数字运行给定命令
batchfile="my_batch_file"

% 指定随机数种子
seed=1903387770

% 启动时打印详细处理器信息
vproc

% 指定记录分解信息的日志文件
logfile="factor.log"

% 将yafu设置为空闲优先级
p

% 重复给定的命令N次
repeat=1



%%% factor选项 %%%

% 在运行NFS之前，ECM是否工作到(pretest_ratio * input_size)位数
pretest_ratio=0.25

% GNFS/SIQS的交叉点(crossover)，以十进制数
xover=100

% SNFS/SIQS的交叉点(crossover)，以十进制数
snfs_xover=85

% 设置(ECM)预测试方案(pretesting plan), 例如plan=light.  
% 以下是有效的选项与他们的比例:
% light (2/9)
% deep (1/3)
% normal (4/13)
% none (0)
% custom (pretest_ratio)
plan=normal

% 仅预测试(rho, p-1, ecm)输入值(即不使用NFS或SIQS)，可选择最大深度
pretest

% 指定在输入上执行ECM的工作量
work=25

% 指定factor期间发现的素数输出文件
op="pfile.dat"

% 指定factor期间发现的因子输出文件
of="factored.dat"

% 指定factor期间未分解数的输出文件
ou="unfactored.dat"

% 对输入值不执行ECM算法
noecm

% 在找到一个因子后就停止
one

% 设置十进制数位数低于N就使用APR-CL算法证明是素数
aprcl_p=500

% 设置十进制数位数高于N就使用APR-CL算法证明是素数，启用额外的信息
aprcl_d=200

%%% QS选项 %%%
% 使用 double-large-prime variation
forceDLP

% 使用 triple-large-prime variation，注意其他选项，该选项可能不会被优化
forceTLP

% 设置小素数变化阈值
siqsTFSm =18

% 指定siqs保存文件名
% qssave="siqs.dat"

% 设置因子基数的大小（要使用的素数）
sqsB

% 设置大于此大小的试分解截止-筛位置(以位为单位)，报告给试验因式分解例程
sqsTF

% 设置筛块数（每边）
siqsNB

% 将大素数界限设置为最大因子基素数的乘数
sqsM

% 不执行小素数变化阈值的优化
noopt

% 设置一个阈值，低于该阈值 siqs 将不使用保存文件（所有关系都是在内存中处理）
inmem=70

%%% NFS选项 %%%
% 运行实验性 cado-nfs+msieve NFS
cadoMsieve

% 包含 CADO-NFS 文件的目录的相对或绝对路径
% 注意：需要在路径末尾添加/或\
cado_dir =/home/nyancat/工具/cado-nfs/

% 指定 convert_poly 可执行文件的路径
% 你可以通过在 CADO-NFS 目录下运行“ make convert_poly ”来构建它
% 它将在 build/*/misc/convert_poly(.exe) 下
convert_poly_path =/home/nyancat/Tools/cado-nfs/build/NyanCatCBLFS.mpi/misc/convert_poly

% 包含 ggnfs-lasieve4I* 可执行文件的目录的相对或绝对路径。
% 没有这些 yafu 将不会使用 NFS
ggnfs_dir =..\..\ggnfs-bin\x64\
% ggnfs_dir =../../ggnfs-bin/

% 逗号分隔的 poly 文件列表以测试sieve
testsieve

% 如果过滤尝试失败，则收集新关系的百分比去生成矩阵
filt_bump=5

% 恢复矩阵求解
ncr

% 强制使用 gnfs（相对于 snfs）
gnfs

% 矩阵求解时使用指定线程数（可以是不同于常规选项的“threads”选项）
lathreads=1

% 重新启动 NFS 作业（当存在现有 nfs.dat 文件时，无论输入如何）
R

% 在搜索多项式前导系数时为每个线程设置一个批量大小
pbatch=250

% 使用代数方格筛分
a

% 使用有理方格筛
r

%%% ECM选项 %%%
% 设置 ECM 的 B1 水平。
B1ecm =11000

% 设置 ECM 的 B2 水平。  
% 仅当您想要默认值以外的其他内容时才需要，默认当前 B1 的百分比。
% B2ecm =1100000

% 指定 ECM 可执行文件的路径
ecm_path =..\gmp-ecm\bin\x64\Release\ecm.exe
% ecm_path =../gmp-ecm/install/mingw/bin/ecm.exe
% ecm_path =../gmp-ecm/bin/ecm

%%% P-1 选项 %%%
% 为 P-1 设置 B1 级别。
% B1pm1 =100000

% 为 P-1 设置 B2 级别。  
% 仅当您想要默认值以外的其他内容时才需要，默认当前 B1 的百分比。
% B2pm1 =10000000

%%% P+1 选项 %%%
% 为 P+1 设置 B1 级别。
B1pm1 =20000

% 为 P+1 设置 B2 级别。  
% 仅当您想要默认值以外的其他内容时才需要，默认当前 B1 的百分比。
% B2pm1 =2000000

%%% Brent-Pollard Rho 选项 %%%
rhomax=200

%%% 费马选项 %%%
fmtmax=1000000