Modular Exponentiation of Complex Numbers | Java implementation of the approach ; Utility function ; Function to multiply two complex numbers modulo M ; Multiplication of two complex numbers is ( a + ib ) ( c + id ) = ( ac - bd ) + i ( ad + bc ) ; Return the multiplied value ; Function to calculate the complex modular exponentiation ; Here , res is initialised to ( 1 + i0 ) ; If k is odd ; Multiply ' complex ' with ' res ' ; Make complex as complex * complex ; Make k as k / 2 ; Return the required answer ; Driver code ; Function call
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static pair Multiply ( pair p , pair q , int M ) { int x = ( ( p . first * q . first ) % M - ( p . second * q . second ) % M + M ) % M ; int y = ( ( p . first * q . second ) % M + ( p . second * q . first ) % M ) % M ; return new pair ( x , y ) ; } static pair compPow ( pair complex , int k , int M ) { pair res = new pair ( 1 , 0 ) ; while ( k > 0 ) { if ( k % 2 == 1 ) { res = Multiply ( res , complex , M ) ; } complex = Multiply ( complex , complex , M ) ; k = k >> 1 ; } return res ; } public static void main ( String [ ] args ) { int A = 7 , B = 3 , k = 10 , M = 97 ; pair ans = compPow ( new pair ( A , B ) , k , M ) ; System . out . println ( ans . first + " ▁ + ▁ i " + ans . second ) ; } }