Bitcoin Forum

maybe i can pay African kids in btc  :)

hmmm,, it depends if the humans have GPU's installed already.

This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 can probably even do it by hand).

Select primes p=11, q=3.
n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = e-1 mod phi = 3-1 mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works...