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