Fermat and Chinese Remainder


  • 13

    If the modulus weren't 1337 = 7 * 191 but a prime number p, we could use Fermat's little theorem to first reduce the exponent to e = b % (p-1) and then compute the result as ae % p. Oh well, we can do it for 1337's prime factors 7 and 191 and then combine the two results with the Chinese remainder theorem. I'll show my derivation of the magic constants 764 and 574 after the solutions below.

    I got the solution using Fermat from @Stomach_ache (thanks) and only added the Chinese remainder theorem stuff to adapt it to non-primes like 1337.

    Solution 1: Python "golf"

    The helper computes ab modulo the prime p.

    def superPow(self, a, b):
        def mod(p):
            return pow(a, reduce(lambda e, d: (10*e + d) % (p-1), b, 0), p) if a%p else 0
        return (764 * mod(7) + 574 * mod(191)) % 1337
    

    Solution 2: C++

    The helper computes ab modulo the given prime.

    int superPow(int a, vector<int>& b) {
        return (764 * superPow(a, b, 7) + 574 * superPow(a, b, 191)) % 1337;
    }
    
    int superPow(int a, vector<int>& b, int prime) {
        if (!(a %= prime)) return 0;
        int e = 0, mod = prime - 1;
        for (int digit : b)
            e = (e * 10 + digit) % mod;
        int pow = 1;
        while (e) {
            if (e & 1)
                pow = pow * a % prime;
            a = a * a % prime;
            e >>= 1;
        }
        return pow;
    }
    

    Using the Chinese Remainder Theorem

    Let's call x = ab. We want to know x % 1337. The helper function using Fermat already gave us u and w so that x % 7 = u and x % 191 = w. Or put differently, x ≡ u (mod 7) and x = w + 191t for some integer t. Combine these to get w + 191t ≡ u (mod 7). Subtracting w and multiplying with [191-1]7 (the multiplicative inverse of 191 modulo 7) we get t ≡ (u-w)·[191-1]7 (mod 7).

    We have [191-1]7 = [(191%7)-1]7 = [2-1]7 and one can easily see that the latter is 4, as (2*4)%7=1.

    Using that, we have t ≡ 4(u-w) (mod 7) or in other words t = 4(u-w) + 7s for some integer s. Which means:

    x = w + 191t
    = w + 191(4(u-w) + 7s)
    = 764u - 763w + 1337s
    = 764u + (1337-763)w + 1337(s-w)
    = 764u + 574w + 1337(s-w)

    So we can compute x from u and v as x = (764u + 574w) % 1337, like I have done in my solutions.


  • 0
    D

    I like this solution: use Fermat's little theorem to set up Chinese Remainder theorem equations. A very representative/general method. However, it might not be the best for this question, because it happens to be the case that 1337 only has two prime factors.


  • 0

    @StefanPochmann great job Stefan. You reminded me of when I studied this stuff in network security (RSA, etc) class :-)


  • 0

    @StefanPochmann said in Fermat and Chinese Remainder:

    If the modulus weren't 1337 = 7 * 191 but a prime number p, we could use Fermat's little theorem to first reduce the exponent to e = b % (p-1) and then compute the result as ae % p.

    Here's the proof of what Stefan is saying, for whom is interested in this stuff: http://math.stackexchange.com/questions/379996/computing-bmods-with-large-exponents-by-paper-and-pencil-using-fermats-littl


  • 0
    W

    this more like a 'back substitution' method rather than Chinese Remainder, anyway, it's such a brilliant approach, I like it very much.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.