Simple Factorization Algorithm

This was my first working factorization algorithm. It's is slow and it has some limitations. Main limitation is that we assume that n (number, for which we search factors) should have exactly 2 prime factors p i q such as p≠q.

From Euler theorem we know that a^φ(n)≡1 (mod n) for every a that is relatively prime to n. Φ(n) is the number of numbers smaller than n that are relatively prime to n.
If n is prime then:
φ(n)=n-1

If n is composite, n = p₁^k₁∙p₂^k₂∙...∙p_j^k_j, then:
φ(n) = (p₁-1)∙p₁^k₁-1 ∙ (p₂-1)∙p₂^k₂-1 ∙ … ∙ (p_j-1)∙p_j^k_j-1
(where j is number of prime factors of n, p_i is one of the prime factors of n and k_i is an exponent of p_i )

Since we assumed that n=p∙q where p and q are prime and p≠q then:
φ(n)=(p-1)∙(q-1)
thus:
φ(n)=n+1-(p+q)

Now all we have to do is to find period t of following generator:
2^k mod n
This is the hardest (most costfull) part, because t~n.
Once we found t we can try to find p and q knowing that t│φ(n).

Code

This algorithm could be easily improved to work for every composite (and to work faster if t is small) using this property: a²≡b² (mod n) → GCD(n,|a-b|)>1. Simply one factor could be obtained by computing GCD(n,st-1) where st is squareroot of 2^t. This will work only if t is even (otherwise we won't find squareroot quickly) and if squareroot is not trivial (ie not 1 or -1)