[原创]crypto-ag真人国际厅网站

# -*- coding: utf-8 -*-

 

"""

用miller-rabin素性测试和离散对数pollard_rho算法进行大数因数分解:

复杂度:0(n^1/4)

适用范围:n 2-10^33

 

"""

import random

from math import log, log10

from collections import counter

 

def gcd(x, y):

    return x if y == 0 else gcd(y, x % y)

 

def fpow(a, x, n):

    ans = 1

    while x > 0:

        if x & 1:

            ans = ans * a % n

        a = a * a % n

        x >>= 1

    return ans

 

# there change the times of rabin-miller

times = 10

def is_prime(n):

    def check(a, n, x, t):

        ret = fpow(a, x, n)

        last = ret

        for i in range(0, t):

            ret = ret * ret % n

            if ret == 1 and last != 1 and last != n - 1:

                return true

            last = ret

        if ret != 1:

            return true

        return false

 

    if not isinstance(n, int):

        raise typeerror(str(n) ' is not an integer!')

    if n <= 0:

        raise valueerror('%d <= 0' % n)

    if n in {2, 3, 5, 7, 11}:

        return true

    for i in {2, 3, 5, 7, 11}:

        if n % i == 0:

            return false

    x = n - 1

    t = 0

    while not x & 1:

        x >>= 1

        t = 1

    for i in range(0, times):

        a = random.randint(1, n - 2)

        if check(a, n, x, t):

            return false

    return true

 

def pollard_rho_2(n, c):

    x = random.randint(0, n)

    i, k, y = 1, 2, x

    while true:

        i = 1

        x = (x * x) % n c

        d = gcd(y - x, n)

        if d != 1 and d != n:

        if y == x:

        if i == k:

            y = x

            k <<= 1

 

def pollard_rho_1(n):

    if not isinstance(n, int):

        raise typeerror(str(n) ' is not an integer!')

    if n == 1:

        return none

    if is_prime(n):

        return [n]

    ans = []

    p = n

    while p >= n:

        p = pollard_rho_2(p, random.randint(1, n - 1))

    ans.extend(pollard_rho_1(p))

    ans.extend(pollard_rho_1(n // p))

    return ans

 

def factorization(n):

    return counter(pollard_rho_1(n))

 

if __name__ == '__main__':

    n = int(input())

    print('len:', len(str(n)))

    print(factorization(n))

原文链接:https://bbs.kanxue.com/thread-266648.htm

网络摘文,本文作者:15h,如若转载,请注明出处:https://www.15cov.cn/2023/08/27/原创crypto-rsa大整数分解-linectf2021-babycrypto3/

发表评论

邮箱地址不会被公开。 必填项已用*标注

网站地图