Concerning the second part of the OP's question:

Also, how can you efficiently find the size of the subgroup $\langle a,b \rangle$ in
$S_n$ ? My crude tests consists of randomly multiplying the two permutations and seeing
how many different elements you get. Maybe there's a more efficient way to generate all
the elements spanned by two permutation.

There is a "classical" polynomial-time method known as the "Schreier-Sims" algorithm for finding the order of the subgroup of $S_n$ generated by a given set of permutations - just google it for further details. It has a number of improvements for dealing with groups of very large degree. Refinements of this were used by Sims to prove the existence of some of the large sporadic finite simple groups, including the Lyons group and the Baby Monster.

There are also very fast "one-sided Monte-Carlo" probabilistic algorithms for verifying that the group generated by a given set of permutations is $A_n$ or $S_n$. If they do, then "yes" will be returned rapidly with high probability. If they do not, then the algorithm does not terminate, so normally you would give up and use Schreier-Sims instead. This method is based on old results due to Jordan and others, which say that if $G \le S_n$ is transitive and contains an element of prime order $p$ with $n/2 < p < n-2$, then $G = A_n$ or $S_n$.

For further details, see Akos Seress' book "Permutation Group Algorithms" Cambridge University Press, 2003, or my own book, with B. Eick and E.A. O'Brien, "Handbook of Computational Group Theory", CRC Press, 2005.