phollard p-1 算法
前置知识：
光滑数：一个可以因式分解为小质数乘积的正整数
如果一个整数是所有素因子都不大于B ，我们陈这个整数是B-Smooth数
如果一个整数的所有素因子的对应指数次幂不大于B，我们称这个整数是B-powersmooth数
eg: 720(24∗32∗5^1) 是一个5-smooth数，6-smooth数，7-smooth数
但51<32<2^4 = 16，所以它也是一个16-powersmooth数
费马小定理：
a ^ (p−1) ≡ 1 (mod p)
算法详解：
1.我们的目的是分解出整数n的因子
2.如果我们可以找到一个与n不互质的整数s，则可以直接通过求gcd(s,n)得到n的一个因子
3.我们的思路转化成如何得到s
4.我们构造x，x满足x ≡ 1 (mod p) ，那么就有gcd(x-1,n) = p，是n的因子
5.再由费马小定理进行转换，2 ^(p-1) ≡ 1 (mod p) ，对比x ≡ 1(mod p)，所以只要求出p-1，就能得到x的值，但是p未知
6.所以考虑如何构造p-1的倍数
7.其实p-1的B-powersmooth数的阶乘就是p-1的倍数
8.所以找到一个合适大小的B，就可以求解
9.找到B之后，回溯：
x ≡ 2 ^(B!) (mod p)
s = x-1
p = gcd(s,n)
例题：
题目：
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flagdef getPrime(bits):while True:n = 2while n.bit_length() < bits:n *= choice(primes)if isPrime(n + 1):return n + 1e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
解密脚本：
from Crypto.Util.number import inverse, long_to_bytes
from gmpy2 import gcdN = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
e = 0x10001a = 2
n = 2while True:a = pow(a, n, N)res = gcd(a-1, N)if res != 1 and res != N:q = N // resprint("n=",n)print("p=",res)print("q=",q)breakn += 1
d=inverse(e,(res-1)*(q-1))
m=pow(c,d,N)
print(long_to_bytes(m))
但是如果题目实际的B很大，该解密脚本可能无法成功解密。并且B越大，爆破的时间越长。