Tagged Questions

1
vote
1answer
135 views

Computational Complexity of Modular Exponentiation

The following was posted from a lecture: "($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method. $Z_1 = a \bmod N$ $Z_2 = (aZ_1) \bmod N$ $Z_3 = (aZ_2) ...
0
votes
0answers
94 views

Collaborative modular exponentiation

EDIT: Rephrased. I have, stored somewhere, the values $a$ , $Q$, $N_1$ (plus its factor) and $a^{2Q} \mod N_1$. I also know $b$, $R$ and $N_2$ (but not its factors). I want to know whether there is ...
1
vote
3answers
378 views

Modular exponentiation?

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation. The method ...