I know that this isn't a math forum .. but i have always found help here so i am posting something again

Given:

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

i.e

gcd(N,M)=2^z

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 ??

Thanks