如何有效地找到 p 是质数的 gcd(a,b) % p？

Question

我的做法很简单：

首先，使用 Euclid 的算法求 gcd(a,b)。
然后用p=10^9+7

但我需要一种有效的方法（只需要正确的轨道而不是代码）：

a 和 b 的值可以在 1 到 10^12 之间，而 p 是prime 10^9+7

Answer 1

如果我遇到你的问题，这将是我的解决方案。在我的解决方案中，我检查long的范围是否可以满足10^12。可以看到下面的代码，它给出了18，表示没问题！尽管如此，我还是不喜欢 Euclid 的 GCD，因为它递归地笨拙地工作。您的范围确实很大这一事实会消耗大量内存。所以，我更喜欢 Binary GCD Algorithm。

class Test {
    private static final long P = (long)Math.pow(10, 9) + 7;

    public static void main(String[] args) {
        // Check whether long is suitable in regards to ranges
        System.out.println((int)Math.log10(Long.MAX_VALUE));
        // Your wish up to 10^12, so it's ok!
        int result = calculate(1, (long) Math.pow(10, 12));
        System.out.println(result);

        result = calculate((long) Math.pow(10, 12), (long) Math.pow(10, 12));
        System.out.println(result);
    }

    public static int calculate(long a, long b) {
        return  (int)(gcd(a, b) % P);
    }

    private static long gcd(long p, long q) {
        // https://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html
        if (q == 0) return p;
        if (p == 0) return q;

        // p and q even
        if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

            // p is even, q is odd
        else if ((p & 1) == 0) return gcd(p >> 1, q);

            // p is odd, q is even
        else if ((q & 1) == 0) return gcd(p, q >> 1);

            // p and q odd, p >= q
        else if (p >= q) return gcd((p-q) >> 1, q);

            // p and q odd, p < q
        else return gcd(p, (q-p) >> 1);
    }

    private static long EuclidianGCD(long a, long b) { return b==0 ? a : EuclidianGCD(b, a%b); }

}

您可以查看here最后一位的答案。另外，如果你非要用Euclid的GCD，试试看，可能会卡死！恕我直言，它无论如何都没有效率。

如何有效地找到 p 是质数的 gcd(a,b) % p？

How to find gcd(a,b) % p efficiently where p is a prime?

java

algorithm

primes

number-theory

greatest-common-divisor