Post your solutions to the Apr 11 In-Class Exercise Thread to this thread. Best, Chris

-- Apr 11 In-Class Exercise Thread

  ModExp(a,x,n)
  input: a, x, n
  output: a^x mod n
    if (x == 1)
      return a mod n;
    b = ModExp(a,x/2,n);
    if (x mod 2 == 0)
      return (b * b) mod n;
    else 
      return (b * b * a) mod n;

I have no idea whats going on. ModExp(a,x,n) input: a, x, n output: a^x mod n if (x == 1) return a mod n; b = ModExp(a,x/2,n); if (x mod 2 == 0) return (b * b) mod n; else return (b * b * a) mod n;

-- Apr 11 In-Class Exercise Thread

 ^ ^ ^ ^ ^
 What he said

 compute_aModN(a, x, n)
 in -> (a, x, n)
 out -> a^x mod n
 
   if x == 1:
     return a mod n
   else:
     * magic *
    return correct answer

^ ^ ^ ^ ^ What he said compute_aModN(a, x, n) in -> (a, x, n) out -> a^x mod n if x == 1: return a mod n else: * magic * return correct answer

-- Apr 11 In-Class Exercise Thread

Name: Kunal Deshmukh <nowiki> Exp-Mod(3, 560, 561) = (Exp-Mod(3, 280, 561))^2 mod 561 = ((Exp-Mod(3, 140, 561))^2 mod 561)^2 mod 561 = (((Exp-Mod(3, 70, 561))^2 mod 561)^2 mod 561)^2 mod 561 = ((((Exp-Mod(3, 35, 561))^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 Let c = Exp-Mod(3, 35, 561) then c= = 3 * (Exp-Mod(3, 17, 561))^2 mod 561 = 3 * (3 * (Exp-Mod(3, 8, 561))^2 mod 561)^2 mod 561 ... to save writing we note Exp-Mod(3, 8, 561) = 3^4 * 3^4 = 81*81 = 390 mod 561 = 3 * (3 * (390)^2 mod 561)^2 mod 561 = 3 * (207 mod 561) ^2 mod 561 = 78 mod 561 Plugging in for c in the above = ((((c)^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 = (((474)^2 mod 561)^2 mod 561)^2 mod 561 = ((276)^2 mod 561)^2 mod 561 = 441^2 mod 561 = 375 mod 561. </nowiki>

-- Apr 11 In-Class Exercise Thread

<nowiki> Solution from the Slides Assumptions: a⋅b and amodb are computable in time proportional to ∣∣a∣∣⋅∣∣b∣∣ (can do grade school algorithms). Exp-Mod(a, x, n) c := (Exp-Mod(a, floor(x/2), n))^2 mod n if x is even return c; else return a * c mod n; Using the algorithm we have: Exp-Mod(3, 560, 561) = (Exp-Mod(3, 280, 561))^2 mod 561 = ((Exp-Mod(3, 140, 561))^2 mod 561)^2 mod 561 = (((Exp-Mod(3, 70, 561))^2 mod 561)^2 mod 561)^2 mod 561 = ((((Exp-Mod(3, 35, 561))^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 Let c = Exp-Mod(3, 35, 561) then c= = 3 * (Exp-Mod(3, 17, 561))^2 mod 561 = 3 * (3 * (Exp-Mod(3, 8, 561))^2 mod 561)^2 mod 561 ... to save writing we note Exp-Mod(3, 8, 561) = 3^4 * 3^4 = 81*81 = 390 mod 561 = 3 * (3 * (390)^2 mod 561)^2 mod 561 = 3 * (207 mod 561) ^2 mod 561 = 78 mod 561 Plugging in for c in the above = ((((c)^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 = (((474)^2 mod 561)^2 mod 561)^2 mod 561 = ((276)^2 mod 561)^2 mod 561 = 441^2 mod 561 = 375 mod 561. Notice this isn't 1, but that's okay as gcd(3,561)=3≠1. </nowiki>

-- Apr 11 In-Class Exercise Thread

 c := (Exp-Mod(a, floor(x/2), n))^2 mod n
   if x is even return c;
   else
     return a * c mod n;

I see that the solution has been uploaded on slide 7 (April 11, 2018). Exp-Mod(a,x,n){ c := (Exp-Mod(a, floor(x/2), n))^2 mod n if x is even return c; else return a * c mod n; }

-- Apr 11 In-Class Exercise Thread

<nowiki> From the Slides Exp-Mod(a, x, n) c := (Exp-Mod(a, floor(x/2), n))^2 mod n if x is even return c; else return a * c mod n; Exp-Mod(3, 560, 561) = (Exp-Mod(3, 280, 561))^2 mod 561 = ((Exp-Mod(3, 140, 561))^2 mod 561)^2 mod 561 = (((Exp-Mod(3, 70, 561))^2 mod 561)^2 mod 561)^2 mod 561 = ((((Exp-Mod(3, 35, 561))^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 Let c = Exp-Mod(3, 35, 561) then c= = 3 * (Exp-Mod(3, 17, 561))^2 mod 561 = 3 * (3 * (Exp-Mod(3, 8, 561))^2 mod 561)^2 mod 561 ... to save writing we note Exp-Mod(3, 8, 561) = 3^4 * 3^4 = 81*81 = 390 mod 561 = 3 * (3 * (390)^2 mod 561)^2 mod 561 = 3 * (207 mod 561) ^2 mod 561 = 78 mod 561 Plugging in for c in the above = ((((c)^2 mod 561)^2 mod 561)^2 mod 561)^2 mod 561 = (((474)^2 mod 561)^2 mod 561)^2 mod 561 = ((276)^2 mod 561)^2 mod 561 = 441^2 mod 561 = 375 mod 561. Notice this isn't 1, but that's okay as gcd(3,561)=3≠1. </nowiki>