0
votes
2answers
36 views

How can I find $x$ such that $ax \equiv 1 \pmod{bx+c}$, given $a,b,c$?

Everything I've read about modular arithmetic generally concerns doing things in some "mod m" world where "m" is some constant. But I'm perplexed how to tackle modular arithmetic problems where the ...
2
votes
1answer
495 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) ...
1
vote
0answers
102 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
940 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 ...