I know that this isn't a math forum .. but i have always found help here so i am posting something again
Find gcd(N,M)Code:N , M , K , gcd(a,b)=1 N,M can be written as N = a + b M = a^2 + b^2 - (2^K - 2) * a * b Note: a,b are not given N ,M ~ 10^400
Now for this i write a brute force code and i always get gcd as a power of two
Hence for finding gcd i use a loop each time multiplying the gcd by 2 and checking if( N%gcd==0 && M%gcd===0 )
But this still ain't fast enough !
Is there any way to compute the gcd faster ??