Modular arithmetic

can some one tell me how to calculate a^F mod m (pow(a,F)%m), where F can be as large as Fibonacci(10^9) and m need not be a prime.( i know how to calculate the above if m is prime).Any reference is appreciated.

This may help you. Or this.

If you need some explanation, feel free to ask… :slight_smile:

1 Like

i know the method that you have used (, but the problem is i may not know F but i know how to compute F (e.g F is Fibonacci(n) and n is variable, 1<n<10^9). in such cases how can i calculate the value. (in the e.g computing F doesn’t help). i need this to solve - Problem BFALG

I’ll look at the question as early as possible, however by your description, it seems, it can be solved by breaking it up into its prime factors and their powers.