素因数计算的费马算法

Question

根据 youtube link 奇数的质因数 可以计算如下：

a = sqrt(N + b^2)

我写了下面的程序来做到这一点，但我没有得到 2345678917 的质因数。我知道这是质数，但对于其他质数，程序会 return 1 和数字本身，但对于这个它没有发生。为什么？

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

void foo(unsigned long long x)
{
    int i;
    for (i=1;i<x;i++)
        if (fmod(sqrt(x + i*i), 1) == 0) {
            printf("%f %f\n", (sqrt(x + i*i) - i), (sqrt(x + i*i)+i));
            return;
        }
}

int main(void) {
    foo((unsigned long long)2345678917);
    return 0;
}

Answer 1

首先，i（int）的类型不匹配x（unsigned long long）。将 i 的类型更改为 unsigned long long 以开始。

一旦你这样做了，你的程序就会高兴地宣布 14 * 167548494 = 2345678917。当然，这不是真的，因为两个偶数的乘积不可能是奇数。这里的问题是精度损失，所以你需要实现一个整数的平方测试函数，而不是测试浮点平方根是否是整数。

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

unsigned long long find_sqrt(unsigned long long x)
{
    unsigned long long lo = 1;
    while (4 * lo * lo <= x) lo *= 2;
    unsigned long long hi = 2 * lo;
    while (lo + 1 < hi) {
        unsigned long long mid = lo + (hi - lo) / 2;
        if (mid * mid <= x) lo = mid;
        else hi = mid;
    }
    return lo * lo == x ? lo : 0;
}

void foo(unsigned long long x)
{
    unsigned long long i;
    for (i=1;i<x;i++) {
        unsigned long long sqrt_x_ii = find_sqrt(x + i*i);
        if (sqrt_x_ii) {
            printf("%llu = %llu * %llu\n",
                   x, sqrt_x_ii - i, sqrt_x_ii + i);
            return;
        }
    }
}

int main(void) {
    foo((unsigned long long) 2345678917);
    return 0;
}

素因数计算的费马算法

Fermat Algorithm for prime factors calculation

algorithm

math

prime-factoring