Russian Peasant Exponentiation

Sort by

recency

|

51 Discussions

|

  • + 1 comment

    Why when I applied the Russian Peasant Exponentiation algorithm on paper for a=8, b=2, k=10, I get c = 60*(2576^2 - 3840^2) - 32*2576*3840*2, which is absolutely a negative number?

  • + 0 comments

    Russian Peasant Exponentiation is a fast and efficient algorithm for computing integer exponentiation using a binary representation of the exponent. It is based on the principle of exponentiation by squaring, which reduces the number of multiplications needed compared to naive repeated multiplication. Tiger Exchange 247.Com Login

  • + 0 comments

    It reduces the number of multiplications required, making it a valuable technique in modular arithmetic and cryptography. Fairplay24.in

  • + 0 comments

    Russian Peasant Exponentiation is an efficient algorithm for computing powers using repeated squaring and multiplication, reducing computational complexity. It showcases the elegance of binary operations in simplifying seemingly complex problems. Betbhai9 id

  • + 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