第四次公钥实验

实验报告

实验内容

相关理论

试除法

Pollard ρ\rho 算法

Pollard p−1p-1 算法

代码分析

sage部分代码分析

试除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# sage 试除法
def find_prime_factors(n):
    factors = []
    if is_prime(n):
        return [n]
    else:
        for i in range(2, n):
            while n % i == 0:
                factors.append(i)
                n = n // i
        if n > 1:
            factors.append(n)
        return factors

test_list = [4279209601, 11626953439, 192311489255622, 16095650737563753533, 45808220048235498832399142287, 149735462706744928439306661202330062437, 548025133786371639137565044874029366557]

for n in test_list:
    start_time = time()
    prime_factors = find_prime_factors(n)
    end_time = time()
    execution_time = end_time - start_time
    print(f"Number: {n}, Prime Factors: {prime_factors}, Execution Time: {execution_time} seconds")

Pollard ρ\rho 算法

Pollard p−1p-1 算法

NTL部分代码分析

试除法

Pollard ρ\rho 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// NTL Pollard rho 算法
#include <NTL/ZZ.h>
#include <NTL/RR.h>
#include <NTL/BasicThreadPool.h>
#include <chrono>

NTL_CLIENT

ZZ func(ZZ n, ZZ c) {
    return SqrMod(n, c);
}

ZZ Pollard_Rho(ZZ n) {
    if (n == 4) return 2;
    if (ProbPrime(n, 50) == 1) return n;
    ZZ x = RandomBnd(n - 2) + 2;
    ZZ y = x;
    ZZ c = RandomBnd(n - 1) + 1;
    ZZ d = 1;

    while (d == 1) {
        x = func(x, c);
        y = func(func(y, c), c);
        d = GCD(abs(x - y), n);
    }

    return d;
}

int main() {
    ZZ tmp_num[] = {4279209601, 11626953439, 192311489255622, 16095650737563753533, 45808220048235498832399142287, 149735462706744928439306661202330062437, 548025133786371639137565044874029366557};
    for (int i = 0; i < 7; i++) {
        auto start = std::chrono::high_resolution_clock::now();
        ZZ factor = Pollard_Rho(tmp_num[i]);
        auto stop = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
        std::cout << "Number: " << tmp_num[i] << " Factor: " << factor << " Execution Time: " << duration.count() << " milliseconds" << std::endl;
    }
    return 0;
}

结果分析

实验数据

数据编号 数据值
1 4279209601
2 11626953439
3 192311489255622
4 16095650737563753533
5 45808220048235498832399142287
6 149735462706744928439306661202330062437
7 548025133786371639137565044874029366557

实验数据生成时间

sage实验数据生成时间
实验 数据 1 数据 2 数据 3 数据 4 数据 5 数据 6 数据 7
试除法
Pollard ρ\rho 算法
Pollard p−1p-1 算法
NTL实验数据生成时间
实验 数据 1 数据 2 数据 3 数据 4 数据 5 数据 6 数据 7
试除法
Pollard ρ\rho 算法
Pollard p−1p-1 算法

sage部分结果截图

试除法

test_img

NTL部分结果截图

试除法
Pollard ρ\rho 算法
Pollard p−1p-1 算法

参考文献

  • 书籍：无
  • 论文：无