rsa n分解问题

Question

可以将 8787377654225918139889809 分解因数得到的结果为{3: 4, 13: 6, 19: 2, 53: 8}
3**4 * 13**6 * 19**2 * 53**8
现在如何通过这个结果得到p和q？

Answer 1

因数分解问题其实是RSA 加密算法里面最简单的问题，因此本题的核心说白了是因式分解问题。

首先定义一个函数 get_pq，它接受一个参数 factors，表示因数分解的结果。这里使用了字典来表示质因数和其对应的指数。
（这其实很像力扣中的哈希表专项练习的思路）

然后在函数内部，我们遍历 factors 字典的每个质因数及其对应的指数。质因数的数学公式相信你应该也很熟悉，就是能不能除以二，所以接下来我们做的事情就是if 判断。

对于每个质因数，我们将其指数除以 2，如果能整除，则认为是 p 的指数；否则，认为是 q 的指数。根据这个规则，我们将质因数的底数进行指数运算并乘积到 p 或 q 中。
最后，主函数里自定义了一个get_pq 函数，这个函数的功能就是打印，并将得到的 p 和 q 输出到控制台。

#include <stdio.h>
#include <math.h>

typedef struct {
    long long base;
    int exponent;
} Factor;

void get_pq(const Factor factors[], int numFactors, long long *p, long long *q) {
    *p = 1;
    *q = 1;

    for (int i = 0; i < numFactors; i++) {
        long long base = factors[i].base;
        int exponent = factors[i].exponent;

        // 将质因数的指数除以 2，判断是否为 p 的指数
        if (exponent % 2 == 0) {
            int p_exponent = exponent / 2;
            *p *= (long long)pow(base, p_exponent);
        } else {
            // 如果质因数的指数不能被 2 整除，则为 q 的指数
            int q_exponent = exponent / 2;
            *q *= (long long)pow(base, q_exponent);
        }
    }
}

int main() {
    Factor factors[] = {
        {3, 4},
        {13, 6},
        {19, 2},
        {53, 8}
    };
    int numFactors = sizeof(factors) / sizeof(factors[0]);

    long long p, q;
    get_pq(factors, numFactors, &p, &q);

    printf("p = %lld\n", p);
    printf("q = %lld\n", q);

    return 0;
}