Quote:
Originally Posted by carpetpool
You seem to have the right idea. You want to calculate 2^n for some integer n. However, this integer n is the one you want to test for primality, and not even 2^n, but 2^n mod n. (n may have, thousands, millions, and maybe even a billion digits). Look up modular or binary exponentiation.

If n is the exponent, as you have clearly indicated, n *cannot* have millions or billions of digits for any meaningful description or test for primality.
The number 2^n may indeed be as large as those descriptions, but the exponent 'n' cannot. 2 raised to a thousandsofdigits number is not an item we contemplate for primality testing, ever.