If p is a prime number other than 2, then using formats thearom it follows the condition:
2^(p-1) mod p = 1
So In order to check whether a number is prime or not, we have to check the value 2^(p-1) mod p.
And 2^(p-1) can be calculated efficiently, by following a binary search strategy. (Refer to the post Raising a number to a larger power)