当前位置：首页 > article >正文

Pollard‘s p-1算法

article 2024/10/21 9:37:18

概述

光滑数 (Smooth number)：指可以分解为多个小素数乘积的正整数

当p是N 的因数，并且p−1是光滑数，可以考虑使用Pollard's p-1算法来分解N

当p是N的因数，并且p+1是光滑数，可以考虑使用Williams's p+1算法来分解N

这里只介绍pollard p-1算法

算法核心

假设存在素数p，p是合数n的因子，p-1可以被分解成多个小素数k1,k2,k3......kn<B(其中B是我们选取的一个上界）

p-1=k1*k2*k3...*kn

那么存在 p-1 | B！

由费马小定理可知：

$m^(p-1) \equiv 1 mod p$

因为p-1 | B！所以

$m^(B!) \equiv 1 mod p$

所以

$m^(B!) - 1= k*p$

而我们的目的就是求出p

于是乎

$p=gcd(m^(B!)-1,n)$

代码实现：这里m取最简单的值：2

#脚本1
def Pollard(B, n):
    a = pow(2, math.factorial(B), n)
    return math.gcd(a-1, n)

math.factorial(B)是求B的阶乘

a = pow(2, math.factorial(B), n) 这里模n可以减小数值，加快计算，否则脚本执行会很慢很慢

#脚本2
m = 2
i = 2
while True:
    a = pow(m, i, n)
    p = gmpy2.gcd(a-1, n)
    if p != 1 and p != n:
        q = n // p
        print("p=",p)
        print("q=",q)
        break
    i += 1

这里没用上界B，而是不断用m乘i，构成阶乘，从而找到上界

案例

2024_newstar_crypto

from Crypto.Util.number import *
from random import choice
from enc import flag

m = bytes_to_long(flag)
def get_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for num in range(2, limit + 1):
        if is_prime[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False
    return primes

def get_Prime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 65537
primes = get_primes(e)
p = get_Prime(512)
q = get_Prime(512)
n = p*q
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 11039465757321779749699115271175512667139900174718736810369447320076323722255434292310358024561522508796910115450323496447022239437773990981536427837406218598107069494432101729405702532145398564394815485237091250665627736733029998539907483103936019387506766847901269370907583069348340970264589547521878184740704877
e = 65537
c = 999985242089285281573358992862050772171553905758195933815934618530062196165616033686130348967500088738894025554769544651219372069639483611911419044407380282591769389311004388591587725946534597210624224229109408954620531714696257219047380587652138116530227788392134058889161962899416080258311278619324733722515967
'''

这里的光滑数是p+1，但本质都是一样的

脚本代码

from Crypto.Util.number import *
from random import choice
from sympy import factorint
import math
import gmpy2

n = 11039465757321779749699115271175512667139900174718736810369447320076323722255434292310358024561522508796910115450323496447022239437773990981536427837406218598107069494432101729405702532145398564394815485237091250665627736733029998539907483103936019387506766847901269370907583069348340970264589547521878184740704877
e = 65537
c = 999985242089285281573358992862050772171553905758195933815934618530062196165616033686130348967500088738894025554769544651219372069639483611911419044407380282591769389311004388591587725946534597210624224229109408954620531714696257219047380587652138116530227788392134058889161962899416080258311278619324733722515967

def Pollard(B, n):
    a = pow(2, math.factorial(B),n)
    return math.gcd(a-1, n)
p=Pollard(e,n)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

flag=pow(c,d,n)
print(long_to_bytes(flag))

查看全文

http://www.kler.cn/news/357107.html