View Single Post
Old 2020-05-15, 18:59   #17
VBCurtis's Avatar
Feb 2005
Riverside, CA

2·3·751 Posts

Originally Posted by carpetpool View Post
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 thousands-of-digits number is not an item we contemplate for primality testing, ever.
VBCurtis is offline   Reply With Quote