We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Russian Peasant Exponentiation
  5. Discussions

Russian Peasant Exponentiation

  • hcy22
     + 0 comments
    1. Conver k into binary then do multiplication
    2. Use mod to keep the value inside the default int range for best performance

    Python code:

    def solve(a, b, k, m):

    def mul(r1, i1, r2, i2):
        return (r1 * r2 - i1 * i2) % m, (r1 * i2 + r2 * i1) % m

    k2 = bin(k)[2:][::-1]

    # dp_i := (a + bj) ^ (2*i), i is index, j is image unit
    dp = (a, b)
    dpi = 0 
    
    real, imag = 1, 0
    for n in range(len(k2)):
        if k2[n] == '1':
            while n != dpi :
                dpi += 1
                dp = mul(*dp, *dp)
            real, imag = mul(real, imag, *dp)
    return real, imag