64^235 mod 391

see: For example:

http://dimacs.rutgers.edu/Workshops/Security/program2/quisquater/node3.html

I just entered this into the calc

mod(64^235,391)

$$\left({{\mathtt{64}}}^{{\mathtt{235}}}\right) {mod} \left({\mathtt{391}}\right) = {\mathtt{4}}$$

I don't know how to do this without the calc  

Notice the pattern, Melody

64^15 mod 391  = 4

64^59mod 391 = 4

64^103mod 391 = 4

Which leads us to believe that this pattern repeats every 44th power

Therefore

64^(15 + 44n)mod 391 = 4 for all positive integers, n

So

64^(15 + 44*5)mod 391  = 64^(15 + 220)mod 391 = 64^(235)mod 391  = 4 ....!!!

Actually, zegroes, there was some "brute force" required in my answer.....I just thought it was an interesting pattern......LOL!!!

LOL!!!

64^235 mod 391

$$\small{\text{
$
\begin{array}{ll}
64^{235} \mod 391\\
=(64^5)^{47}\mod 391 &\quad | \quad (64^5) \mod 391 = 302 \\
= (302)^{47}\mod 391 \\
= 302^2 *(302)^{45}\mod 391 \\
= 302^2 *(302^3)^{15}\mod 391 &\quad | \quad (302^3) \mod 391 = 4 \\
= 302^2*4^{15}\mod 391\\
= 302^2*(4^3)^{5} \mod 391 &\quad | \quad 4^3= 64 \\
=302^2*(64)^5 \mod 391 &\quad | \quad (64^5) \mod 391 = 302 \\
=302^2*302 \mod 391\\
=302^3 \mod 391 &\quad | \quad (302^3) \mod 391 = 4 \\
= 4 \mod 391
\end{array}
$
}}$$

Thanks Heureka, I'll try and remember that.  :) 

Thanks Chris but I think Heureka's makes mores sense. :))

I have tucked this one away in "reference material"  

It's just a different approach....whether it "makes more sense" is debatable....

I think that mine is perfectly valid....

See:

Square-and-Multiply-Algorithm with modulo for any $$\small{\text{$b^x\mod n$}}$$

Is that meant to take me somewhere Heureka??

Thanks Heureka 

long modulo( long b, long x, long n) { // b = basic, x = exponent, n = modulo

   long z=1; b=b % n;

   while (x !=0) {

      if (x%2 !=0) z = (z*b)%n; // Exponent odd

      b =(b*b)% n; x = x/2;

  } // while

  return z;

}

Square and Multiply Algorithm:

$$64^{235} \mod{391}$$

$$\small{\text{
$
\begin{array}{lr}
Exponent&z=1\\
&64 \mod 391 = 64 = b\\
\hline
235\ odd: &\underbrace{1*64}_{=z*b} \mod 391 = 64 = z\\
&(\underbrace{64}_{=b})^2 \mod 391 = 186 = b \\
:2 & \\
\hline
117\ odd: &\underbrace{64*186}_{=z*b} \mod 391 = 174 = z\\
&(\underbrace{186}_{=b})^2 \mod 391 = 188 = b \\
:2 & \\
\hline
58\ even: &(\underbrace{188}_{=b})^2 \mod 391 = 154 = b \\
:2 & \\
\hline
29\ odd: &\underbrace{174*154}_{=z*b} \mod 391 = 208 = z\\
&(\underbrace{154}_{=b})^2 \mod 391 = 256 = b \\
:2 & \\
\hline
14\ even: &(\underbrace{256}_{=b})^2 \mod 391 = 239= b \\
:2 & \\
\hline
7\ odd: &\underbrace{208*239}_{=z*b} \mod 391= 55= z\\
&(\underbrace{239}_{=b})^2 \mod 391 = 35= b \\
:2 & \\
\hline
3\ odd: &\underbrace{55*35}_{=z*b} \mod 391= 361 = z\\
&(\underbrace{35}_{=b})^2 \mod 391 = 52= b \\
:2 & \\
\hline
1\ odd: &\underbrace{361*52}_{=z*b} \mod 391= \textcolor[rgb]{1,0,0}{4} = z\\
&(\underbrace{52}_{=b})^2 \mod 391= 358= b \\
:2 & \\
0\ end
\end{array}
$
}}$$

Thanks once agaain Heureka