4
$\begingroup$

I am studying for a cryptography final and I have come across something I can just not figure out. My math background is rather weak.

This is related to RSA and concerns itself with raising numbers to large powers. The question is:

Compute $10^{237}\mod 1009$.

I am aware the answer is $852$, but I am unable to calculate it.

I have tried using multiple of powers and looked at Euler's theorem and also Fermat's theorem, but at this point I'm so confused!

Any help would be appreciated.

$\endgroup$
  • 4
    $\begingroup$ Repeated squaring would work quite easily here (you'd need to calculate ~8 residues). $\endgroup$ – apnorton Jan 9 '15 at 17:07
17
$\begingroup$

$1009$ is a prime number and multiplicative groups modulo prime numbers are cyclic, so some numbers have order $1008$, so you won't be able to apply euler fermat or any result relying on the order of the elements.

Here is how exponentiation by squaring works: write the exponent in binary.

$237=11101101$

Proceed to calculate $10,10^2,10^4,10^8,10^{16},10^{32},10^{64},10^{128}$ in base $1009$ by squaring the previous term.

You should get $10,100,919,28,784,175,355,909$.

Since $10^{237}=10^{128}*10^{64}*10^{32}*10^{8}*10^{4}*10$ you want

$909\cdot355\cdot175\cdot28\cdot919\cdot 10 \bmod 1009$ to calculate this simplify mod $1009$ after each multiplication.

Your final result should be $852$

$\endgroup$
  • 1
    $\begingroup$ Thank you Modded Bear, this was clear precise and very helpful! I appreciate it $\endgroup$ – Joe Connell Jan 9 '15 at 18:04
  • 3
    $\begingroup$ Also, you may want to write some congruences in negative form instead of positive form to ease calculations. for example $919$ is $-90$, notice when you square the sign becomes positive anyway. $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '15 at 18:34
4
$\begingroup$

The Algorithm:

  • Input: $x=10,e=237,n=1009$

  • Output: $y=1$

  • Repeat until $e=0$:

    • If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

    • Set $x=x^2\bmod{n}$

    • Set $e=\lfloor\frac{e}{2}\rfloor$

C Implementation:

int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(10,237,1009);
$\endgroup$
  • $\begingroup$ what does "e>>=1;" do? $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '15 at 18:02
  • $\begingroup$ @ModdedBear: As the algorithm description (above) says, it sets $e=\lfloor\frac{e}{2}\rfloor$. $\endgroup$ – barak manos Jan 9 '15 at 18:03
  • 2
    $\begingroup$ Oh, I get it now. $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '15 at 18:05
  • $\begingroup$ Thank you barak, as a programmer i do appreciate this precise code but it has to be done by hand. I cant upvote as i do not have enough rep but thank you for your help $\endgroup$ – Joe Connell Jan 9 '15 at 18:05
  • $\begingroup$ @JoeConnell: You're welcome. Don't worry about the up-voting :) As to "be done by hand" - I added the general algorithm above the code, so it might be helpful to you with that task of yours. $\endgroup$ – barak manos Jan 9 '15 at 18:09
0
$\begingroup$

Some useful theorems about modular arithmetic. I'm using $\%$ as a modulo operator here, since I think you're working in a computational context.

$$(ab) \% m = ((a \% m)(b \% m)) \% m$$

This leads to:

$$(a^{2n}) \% m = (((a^2)\% m)^n) \% m$$ and $$(a^{2n+1}) \% m = (a (((((a^2)\% m)^n) \% m)\%m$$

Which leads to the fast modular exponentiation algorithm, which requires $O(\log n)$ operations.

// calculates (b * a^n) mod m, with no intermediates 
// getting larger than m^2

powmod2(a,b,n,m) =
    if (n = 0) then return (a % m)
    if (n is odd) then return powmod2(a,(b*a)%m,n-1,m)
                  else return powmod2((a*a)%m,b,n/2,m)

Which is more commonly implemented like this:

// calculates a^n mod m with no intermediates
// larger than m^2
int powmod(a,n,m) {
    int accum = 1;
    a = a % m;
    while (n > 0) {
        if (n % 2 == 1) { // n is odd
            accum = (accum * a)%m;
            n = n - 1;
        } else { // n is even and greater than 0
            a = (a*a)%m;
            n = n / 2;
        }
    }
    return accum;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.