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

Question

My approach is very simple:

• First, Finding gcd(a,b) using Euclid's Algorithm.
• Then taking out mod with p=10^9+7

But I need an efficient way (just need the right track not code):

Values of a and b could in between 1 to 10^12 whereas p is a prime 10^9+7

Answer 1

It would be my solution if I had an problem as yours. In my solution, I check the range of long whether it may satisfy 10^12. As you can see the following code, it gives 18, which means it's ok! Nonetheless, I wouldn't prefer Euclid's GCD because it works lumbering recursively. The fact your range is really big gives rise to consuming a host of memory. So, I'd prefer 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); }

}

You can check answer of the last one from here. Besides, if you insist on usage of Euclid's GCD, try it, it may be stuck! and IMHO it is not efficient whatsoever.