每日10行代码173:测试下yafu的质因数分解能力

在做rsa题目时，经常会遇到因素分解的问题，而因素分解里有一个很出名的工具叫yafu.
yafu的介绍是：
当p、q的取值差异过大或过于相近的时候，使用yafu可以快速的把n值分解出p、q值
但是什么是过大或过于相近呢？
我写了以下代码进行测试：

import libnum
import gmpy2

p=libnum.generate_prime(1024)
#下一个素数
q=gmpy2.next_prime(p) 
for i in range(1,100):
    q=gmpy2.next_prime(q) 
print("p:",p)
print("q:",q)
print("p*q:",p*q)
print("p/q:",p/q)
print("q-p:",q-p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

p: 141566772919618364127744850865533440414451206413310552358860619218346041489973446709470153037832406595022828277505378043753937827321848214778611319490135099441024368353503518118174023614228762435821890903396216072465699868586873318521161771813178260640162972593382571988438922009337540098233641719966903998293
q: 141566772919618364127744850865533440414451206413310552358860619218346041489973446709470153037832406595022828277505378043753937827321848214778611319490135099441024368353503518118174023614228762435821890903396216072465699868586873318521161771813178260640162972593382571988438922009337540098233641719966904070799
p*q: 20041151194874791408668803994299467976146838731991726041835833756559457643526796140805936752400765487514377896972405104255857736705179851571753546042304842281851730609772928345843285007556770393502638715132818326956700372923695896246632931021336910629173334552735362800684809455265510119627798422002699203587594064154692733408095125279526506070337909800902123390255376612555517959503622606047125811497069585133574857573750212622547932170832463777309717491271075702255996884402738913944970999953396182243784413123496990742310169940156972588999353996804299428022670005102722161765894588291597654429629061169331047146107
p/q: 1.0
q-p: 72506
1
2
3
4
5

从这个输出也可以看出，p到q间间隔了100个素数，而差值为72506，平均每两个素数之间的差是725，72506相对于这个大素数来说还是很小，以致于他们之间比值还是1.0

把p*q的值放到yafu里分解：

yafu-x64.exe factor(20041151194874791408668803994299467976146838731991726041835833756559457643526796140805936752400765487514377896972405104255857736705179851571753546042304842281851730609772928345843285007556770393502638715132818326956700372923695896246632931021336910629173334552735362800684809455265510119627798422002699203587594064154692733408095125279526506070337909800902123390255376612555517959503622606047125811497069585133574857573750212622547932170832463777309717491271075702255996884402738913944970999953396182243784413123496990742310169940156972588999353996804299428022670005102722161765894588291597654429629061169331047146107) 

>>输出结果：
>fac: factoring 20041151194874791408668803994299467976146838731991726041835833756559457643526796140805936752400765487514377896972405104255857736705179851571753546042304842281851730609772928345843285007556770393502638715132818326956700372923695896246632931021336910629173334552735362800684809455265510119627798422002699203587594064154692733408095125279526506070337909800902123390255376612555517959503622606047125811497069585133574857573750212622547932170832463777309717491271075702255996884402738913944970999953396182243784413123496990742310169940156972588999353996804299428022670005102722161765894588291597654429629061169331047146107
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 7.4970 seconds


***factors found***

P309 = 141566772919618364127744850865533440414451206413310552358860619218346041489973446709470153037832406595022828277505378043753937827321848214778611319490135099441024368353503518118174023614228762435821890903396216072465699868586873318521161771813178260640162972593382571988438922009337540098233641719966904070799
P309 = 141566772919618364127744850865533440414451206413310552358860619218346041489973446709470153037832406595022828277505378043753937827321848214778611319490135099441024368353503518118174023614228762435821890903396216072465699868586873318521161771813178260640162972593382571988438922009337540098233641719966903998293

ans = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

后续，我又进一步计算了下：
当两个素数之间间隔1000个素数时，发现平均素数间隔是645。
当两个素数之间间隔10000个素数时，发现平均素数间隔是715。

最后发现这种方法还是太慢，我直接按比例增长：

import libnum
import gmpy2

p=libnum.generate_prime(1024)
#下一个素数
q=gmpy2.next_prime(int(p*1.05)) 

print("p:",p)
print("q:",q)
print("p*q:",p*q)
print("p/q:",p/q)
print("q-p:",q-p)
1
2
3
4
5
6
7
8
9
10
11
12

输出结果：

p: 115572347070016580215507242308636343714210069363622314287140999792738235445053532383274708312874784322670865444911536762108855282843662652806238996805302247524895835402769172349629358340259633765420691596422482340934922563816048656742734554186269128120676349840177382723512014064696579032015103670724774092809
q: 121350964423517405861358958915115678810075337286855436744382211045320123771644810025295114971465769128604633186552644004980318729421288815446886030632729931648198264438139737674706237295462105739661137137892522985141269061157682835459446449109852570550505968058612171538938921651681284618083839036390213943503
p*q: 14024815777635988125537183514586475274219183779665756062194214981118406731889656474398388439702313017575189435154693113870916861478994183647714504658282456384480108314528066155036837708616833959200189522607876841776519707819946773920421802987354179710930633719872269551037408432988223352888756743059592276438398613457443019314056802135839475751450397926988090990936372228677724138679431980054372529723965521353224512901791488075045782537224757517146754948086587842475213923223902052868316025452705307875989597418054733484528558727035032993966935566847153327008893248379253347129590715044418685231766005037809204569927
p/q: 0.95238095238095244
q-p: 5778617353500825645851716606479335095865267923233122457241211252581888326591277642020406658590984805933767741641107242871463446577626162640647033827427684123302429035370565325076878955202471974240445541470040644206346497341634178716711894923583442429829618218434788815426907586984705586068735365665439850694
1
2
3
4
5

把p*q的值放到yafu里分解，发现还是可以分解的，只是时间要的很长，目前显示需要的时间为25小时，还不知道最张时间会不会再增长。
最后，经过反复测试
当p和q的差值相比于p和q的数量级来说，几乎很小时，才能很快分解出来p和q，当当p和q的差值相比于p和q的数量级来说，达到1%，0.1%时，用yafu分解就几乎分解不出来了。

以上仅为一次试验得出的结论，仅供参考，不具有普遍性。