if gcd(b, N) == 1: assert pow(b, totient(N), N) == 1Also, if public key N = p*q with p,q being big probable primes per Miller-Rabin, then the totient(N) is simply (p-1) * (q-1).
Using the Extended Euclidean Algorithm (EEA), we compute: d = inverse(e, totient(N)) such that (e*d) % totient(N) == 1.
So now d is the secret complement of public key N, presumably not derivable minus knowledge of factors p and q, and presumably N can't be factored in any reasonable amount of time (win big bucks if you're able to crack these large Ns).
Then RSA works essentially as follows:
ciphertext = pow( plaintext, e, N)I've got more discussion of all this at the Math Forum under the heading of Gnu Math.
plaintext = pow( ciphertext, d, N)