El Gamal: solve "a" for "h = g^a (mod p)" Currently trying to understand cryptography by myself. There is a task of forging El Gamal signature 
p=541, g=2, h=419 and are public keys.
I need to find a, which is a private key.
The only info I found so far is that the whole task is somehow related to the discrete logarithms.
 A: For these small values use Pollard's rho. My implementation found
$a=66$ in $22$ iterations.
For more info see the Wikipedia entry for Discrete logarithms and especially the algorithm section.
A: If p-1 has a decent number of prime divisors, it can be done relatively fast, using the chinese remainder theorm and a bit of tricks.  I ran a program that hunted down these sorts of numbers for every prime under two million.
In essence, we note that 540 = 2*2*3*3*3*5, and proceed from there.
Find 2^270 and h^270.  as 540 and 1
Find 2^135 and h^135.  as  52 and 540.  Thus a = 2, mod 4

Find 2^180, h^180  as 129, 1   Thus a = 0, mod 3
Find 2^60, h^60  as  15, 129   Thus a = 3, mod 9
Find 2^20, (64*h)^20 as 411

We've added 2^6 to h, and found that the nineth power of this is 411 = 129^2.  This means that h+6 = 18, mod 27, and thus h = 12, mod 27
Find 2^108, 419^108. = 48, 48.  

We scroll through the powers of 48 until we get a match, but h mod 5 = 1.
So, modulo(4, 27, 5), we seek (2,12,1).
We have 108 = (0,0,3), so 216 = (0,0,1)   add 216
We have 20  = (0,20,0), so 80 = (0,-1,0)  add -960
We have 135 = (3,0,0) so 405 = (1,0,0)   add 810

216-960+810 = 66
This particular algorim is considerably fast when p-1 has a large number of small divisors.  
