2
$\begingroup$

Sorry for my English, it's not my first language and that's a lot more evident when we talk about math.

I'm currently taking a cryptography class in university and we have to deal with very big mod numbers, I'm familiar with using Fermat and Euler to deal with large exponents on things like $$6^{219} \pmod{35}$$ But now I'm trying to deal with smaller numbers, and I just can't seem to find a way out, for example, lets say: $$19^3 \pmod{55}$$ Is there a quick way to solve smaller cases like this? Sure I could easily go through the math, but on a very large exam on a very tight timer, I would like to minimize my number crunching time, I'm just wondering, is there a theorem or anything of the sorts to sort stuff like this?

  • 0
    Very related (and possibly a duplicate): http://math.stackexchange.com/questions/36318/modulo-arithmetic-with-big-numbers2012-01-13
  • 1
    @JavaMan: I don't think it's really a duplicate: here Joao is asking for minimizing computation with *small* exponents; repeated squaring here would not help, since you would end up having to compute $19^2$ and then multiplying the result by $19$, which means you are just computing $19^3$.2012-01-13
  • 1
    @ArturoMagidin: That's fair. I could have gone either way, but I agree.2012-01-13

1 Answers 1