This is what you did in 1st grade... Theoretical runtime: O(exp(#of digits in n))  not good 
A tweaked around version of Fermat's Method. Theoretical runtime: O( unknown ) 
Uses group theory... Theo. runtime: O(exp(#of digits in n))  also, not good 
No clue on this one... yet... Theo. runtime: unknown 
No clue on this one... yet... Theo. runtime: unknown 
Based on 'Fermats Little Theorem' Theo. runtime: O(q) (where q is largest factor of p1)  "eh" 
Simple and very effective algorithm Theo. runtime: O(sqrt(p))  not bad 
Theo. runtime: O( exp(sqrt(2*ln(n)*ln(ln(n))) ) 
Theo. runtime: sub exponential 
You should understand this if you want to understand Dixon's alg. Theoretical runtime: O(exp(#of digits in n))  not good 
You need to understand this if you want to understand MPQS or NFS. Theo. runtime: sub exponential 
A supped up, hod rodded version of Dixon's algorithm... Theo. runtime: same as eliptic curve 
The hot algorithm of the 90's... Theo. runtime: O(exp(c*(ln(n)^1/3*ln(ln(n)^2/3)))  darn good 
Used to be hip, now just a relic. Theo. runtime: O( exp(sqrt( ln(n)*ln(ln(n)) )) )  good 
Theo. runtime: sub exponential 
Theo. runtime: sub exponential 
