This is a Diffie-Hellman / RSA style algorithm. The big difference between the two is key exchange, which isn't covered here.

key generation

randomly find two prime numbers p and q
The total bits of these represent the encryption strength.
ex: if p = 7 and q = 17, p is 3 bits, q is 5 bits, so this would be 8 bit encryption.
calculate the modulus, n = p * q
ex: if p = 7 and q = 17, n = 7 * 17 = 119
calculate the totient, c = ( p - 1 ) * ( q - 1)
ex: if p = 7 and q = 17, c = 6 * 16 = 96
randomly select a private key e such that e and c are relativly prime, and 0 < e < c
Relatively prime is equivalent to meeting the condition of gcd(e,c) = 1.
ex: 96 factors into 2⁵3, so e can be any number that does have a factor of 2 or 3.
ex: e = 5
find a public key d such that ( d * e mod c = 1 ) and 0 < d < c
This is the operation that we refer to as a discrete logarithm. There should be one and only one positive value that works. This number will be relatively prime to c and e.
ex: ( 77 * 5 ) % 96 == 1, so the public key d = 77

Here are the values in our example:

primes p = 7 q = 17
modulus n = 119
totient c = 96
private key e = 5
public key d = 77

Only three of these values are retained modulus n, private key e, and public key d. The public key and modulus are made available to everyone, these values are used to encrypt messages. The private key must be kept private, and is the value used to decrypt messages along with the modulus. Note: The labels for d and e may be inverted on some algorithms, but it doesn't really matter as long as onnly one key is made public.

encryption

You must have the public key d for the recipient and the modulus n. Given a plaintext message m, the cyphertext s is defined as

s = m^d % n

ex: if m = 97 ( ascii 'a' is decimal 97 )
s = 97⁷⁷ % 119 = 48

decryption

You must have the private key e for the recipient and the modulus n. Given a cyphertext s, the plaintext message m is defined as

m = s^e % n

ex: if s = 48
m = 48⁵ % 119 = 97 ( this is the original 'a' that we encoded )

Cracking

To attack this algorithm, we need to work backwards. All we know is the following :

modulus n = 119
public key d = 77

We need to compute the private key e.
Here are the steps to solve it.

factor n = 119
The factors are 7 and 17. We only need to find one factor, since we know that n = p * q, where p and q are prime, if we find p, q = n / p.
compute the totient c
c = (7-1) * (17-1) = 96
compute the discrete log to get the private key e
( 77 * e ) % 96 = 1
( 77 * 5 ) % 96 = 1, so e = 5

Here are some of related algorithms that are not too complex but reasonably efficient. I use the following notation : exponents ^, modulus %, multiplication *, division /.

Pollard rho factoring method

n = number to factor
x[0] = some small prime non-factor ( ex: 2, 3, 5 )

x[i] = ( x[i-1] ^ 2 + 1 ) % n 
y[i] = x[2*i] 

factor = gcd( | y[i] - x[i] |, n )
If factor != n OR factor != 1, then it is a factor of n.

ex : I want to factor 119.
x[0] = 2;
x[1] = 2^2 + 1 % 119 = 5
x[2] = 5^2 + 1 % 119 = 26

y[1] - x[1] = 21
gcd(21,119) = 7

If I compute a factor of 2056609237 with x[0] = 2, I get the answer at x[44] ( the result is 827 ).

Euclidean greatest common divisor

gcd(x,y)

x < y , and both are positive

while( x != 0 )
{
    a = y / x
    b = y % x
    now we know that : y = a * x + b
    y = x
    x = b
}

y is the gcd

ex :

gcd( 21 , 119 )
119 = 5 * 21 + 14
21 = 1 * 14 + 7
14 = 2 * 7 + 0
gcd = 7

Here is the bc code for the gcd stuff

Extended Euclidean algorithm

This is a good way to compute a discrete logarithm or multiplicative inverse. When the GCD(x,y) = 1 then x has a multiplicative inverse modulo y, where x < y and x^-1 < y in a fashion such that x * x^-1 = 1 % y.

(A1, A2, A3) = (1, 0, y)
(B1, B2, B3) = (0, 1, x)

when B3 = 0 then there's no inverse
when B3 = 1 then B2 is the multiplicative inverse

Q = int(A3/B3)

(Z1, Z2, Z3) = (A1 - Q * B1, A2 - Q * B2, A3 - Q * B3)

(A1, A2, A3) = (B1, B2, B3)
(B1, B2, B3) = (Z1, Z2, Z3)


ex :  we want the inverse 77 modulo 96

gcd(77,96)

Q   A1   A2   A3   B1   B2   B3     A3' = Q * A3 + B3
-------------------------------     ---------------
-    1    0   96    0    1   77
1    0    1   77    1   -1   19     96 = 1 * 77 + 19
4    1   -1   19   -4    5    1     77 = 4 * 19 + 1
19  -4    5    1   77  -96    0     19 = 19 * 1 + 0

The multiplicative inverse of 77 mod 96 is 5.

I actually went past the inverse computation.  The gcd computation is 
finished when B3 is 0, the inverse is done when it reaches 1.  In doing 
this the answer moves from B2 to A2, but I can use this for gcd too.

The inverse is A2 = 5
The gcd is A3 = 1

Note : The inverse could be negative, if so just recompute as y + inverse.  
That is the same as inverse % y.