How to compute $2^{\text{some huge power}}$

Question

I have to compute $$2^{p-1} \mod p$$ and show by Fermat's little theorem that $p$ isn't prime. I know what the question is asking but I'm not sure how to reduce the exponent on $2^{p-1}$ to a more reasonable number. Does that make sense? Any general tips would be appreciated.

Answer 1

Exponentiation by squaring is the way to go.

First write the exponent in base two: $322=101000010_{\text{two}}$

Compute $2^n\pmod{323}$: $$ \begin{array}{} 2^n&n&\text{operation (mod $323$)}\\ \hline 1&0_{\text{two}}&\text{initialize}\\ 2&1_{\text{two}}&\text{square and multiply by $2$}\\ 4&10_{\text{two}}&\text{square}\\ 32&101_{\text{two}}&\text{square and multiply by $2$}\\ 55&1010_{\text{two}}&\text{square}\\ 118&10100_{\text{two}}&\text{square}\\ 35&101000_{\text{two}}&\text{square}\\ 256&1010000_{\text{two}}&\text{square}\\ 257&10100001_{\text{two}}&\text{square and multiply by $2$}\\ 157&101000010_{\text{two}}&\text{square}\\ \end{array} $$

---

Explanation of the Method:

When we square $a^n$, we double the exponent: $$ \left(a^n\right)^2=a^{2n} $$ When we square $a^n$ and multiply by $a$, we double the exponent and add one: $$ \left(a^n\right)^2\times a=a^{2n+1} $$ Write the exponent in base two.

Squaring our number doubles the exponent (shifting it left by one bit). Multiplying the number by the base adds one to the exponent.

The goal is to get the desired exponent ($322=101000010_{\text{two}}$), building it up from the left, by shifting left and optionally adding one, when needed. Every time we shift the exponent, we square our number. Every time we add one to the exponent, we multiply our number by the base.

Answer 2

$\large\color{#888888}{\mbox{Following}}\ {\tt\mbox{@Daniel Fischer}}\ \color{#888888}{\mbox{comment}}$:

/* mod_0.cc
http://math.stackexchange.com/questions/553472/how-to-compute-2-textsome-huge-power/553810#553810
*/
#include <iostream>
using namespace std;
typedef unsigned long long ullong;
const ullong ONE=ullong(1),N323=ullong(323),N322=ullong(322);


int main()
{
 ullong expo=ONE;

 for ( ullong n=0 ; n<N322 ; ++n ) {
     if ( (expo<<=ONE) >= N323 ) expo%=N323;
 } 

 cout<<"REMAINDER = "<<expo<<endl;
 return 0;
}

After running the program:

REMAINDER = 157

With $\tt WolframAlpha$: $$ 2^{322}\,{\rm mod}\,323 = \color{#ff0000}{\Large 157} $$