# Test whether an element g of Sn has a cycle of prime
# length p with n/2 < p < n-2
# Note that it is enough to test whether the prime 
# divides the order as we are considering primes > n/2

IsPurpleElement := function(g,n)

        local p, o, i;

        if not IsPerm(g) then Error("First argument not a permutation"); fi;

        if LargestMovedPointPerm(g) > n then
            Error(g," is not in S", n, "\n" );
        fi;

        # Factorise the order of the element g
        # o[i][1] is a prime and o[i][2] the power
        o := Collected(Factors(Order(g)));
      
	    for i in [ 1..Length(o) ] do
   		    if o[i][1] > n/2 and o[i][1] < n-2 then
		        return true;
            fi;
        od;

	return false;

end; 


ContainsAlternatingGroup := function(grp, N)

	local n, i, g;

    if not IsPermGroup(grp) then 
        Error("First argument not a permutation group"); 
    fi;

	n := Size( MovedPoints(grp) );

	if n <= 8 then
		Print(n , " too small, theory does not apply\n");
		return fail;
	fi;


	if not IsTransitive(grp, MovedPoints(grp) ) then
		return false; 
	fi;

	i := 1;
	while i <= N do
		g := PseudoRandom(grp);
		if IsPurpleElement(g,n) then
			return [ true, i ];
		fi;
		i := i + 1;
	od;

	return fail;
end;


FindNCycle := function (grp, n, nr)

	local i, g;


	i := 1;
	while  i <= nr  do
		g := PseudoRandom(grp);
		if g^n = One(grp) then
			return [g, i];
	    fi;
		i := i + 1;
	od;


	return fail;

end;