Let's suppose we have this function:
$f(n)= a^n b^{n-1} c^{n-2} \mod p$, where $a,b,c,p \in Z^*$ and $p$ is also a prime.
I want to create software in C, Java, etc., that calculates the function above, so I thought I can do this:
$f'(n)= (a^n \mod p) (b^{n-1} \mod p) (c^{n-2} \mod p)$
Also an another approach is the following:
$f''(n)=(a^n \mod p) (b^{n-1} c^{n-2} \mod p)$
Is $f(n) = f'(n)=f''(n)$?
In other words I am asking whether I can calculate portions of this function with a modulus to the prime. The reason why I am asking is because I want to perform a cryptographic Burmester Desmedt Key agreement key agreement:
And on the last part I need to calculate separately the $k^{nx_i}$ and the API offers me method with modular exponentiation only. To be more specific the method for modular exponantion is WAY faster than the one offering exponantion only.
They are equivalent but you have to remember to take one more mod $p$ at the end, because the product of two numbers between 0 and $p-1$ could be bigger than $p$:
$$f'(n)= ((a^n {\rm\,\,mod\,\,} p) (b^{n-1} {\rm\,\,mod\,\,} p) (c^{n-2} {\rm\,\,mod\,\,} p)) ({\rm\,\,mod\,\,} p)$$
and similarly for $f''$. Depending on the size of the numbers, you might even want to take ${\rm\,\,mod\,\,p}$ at every step (or every few steps) of the multiplication so your intermediate values don't get too large.