The determination of the Galois group of a polynomial The GAP package has a function $\mathtt {GaloisType}$ that takes a polynomial as an argument and returns a number, the index of the transitive group of order the degree of the polynomial. I read somewhere that the algorithm is based on a theorem by Dedekind based on how the polynomial factors if taken modulo some primes. But this theorem only gives a postive answer about the existence of a cycle, if it finds it, but this gives no certainty about what the group actually is. I also know that there are some probability theorems concerning this problem, but I don't now what they state. What is the probability that the answer is wrong?  
 A: What is happening is a 2-stage process. First Dedekind's theorem is used to obtain some cycle shapes. This gives a lower bound for the Galois group.
Afterwards, polynomials that correspond to the action of the Galois group on k-sets or k-sequences are factored. (E.g.
$$\prod_{i,j} (x-(\alpha_i+\alpha_j))$$
corresponds to the action on 2-sets.)
This way one shows that the Galois group can't be larger. The result is (modular programming errors) proven  correct.
IF you only want a probabilistic result, based on Chebotarev's theorem, the function $\mathtt {ProbabilityShapes}$ does so (and is much faster).
At the risk of shameless self-promotion,
http://www.math.colostate.edu/~hulpke/talks/galoistalk.pdf
are slides of a relevant talk,
http://www.math.colostate.edu/~hulpke/paper/gov.pdf
a survey paper.
A: It seems the comment field is limited, thus a second answer as example:
What you describe is quite possible (and a plausible and intelligent question):
Take $p(x)=x^3+x^2-2x-1$ (the minimal polynomial of E(7)+E(7)^6, so one can actually work with roots). This is irreducible over the rationals and has Galois group A3, so factoring modulo primes will only ever give irreducible or 3 linear factors. Now both A3 and S3 are transitive on 2-sets, so we need to (white lie! see at the end) take 2-sequences.
We therefore form the polynomial whose roots are of the form $\alpha_i+2\alpha_j$. We can do so by calculating the resultant
$r(x)=res_y(2^3\cdot p(y/2),p(x-y))$, and dividing off (the case $i=j$) the factor $3^3p(x/3)$.
gap> r:=Resultant(2^3*Value(p,y/2),Value(p,x-y),y);           
x^9+9*x^8+x^7-168*x^6-308*x^5+609*x^4+1463*x^3-363*x^2-1062*x+351
gap> r/3^3/Value(p,x/3);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13

In practice, a method based on symmetric functions is easier
gap> TwoSeqPol(p,2);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13

produces the same result. If we factor this polynomial of degree 6, we get two factors of degree 3 -- two orbits on 2-sequences. If the initial polynomial had had Galois group S3, it would have stayed irreducible.
You can observe what GAP is doing by setting
SetInfoLevel(InfoGalois,3);

Then GaloisType will print information about the process, e.g.
gap> GaloisType(x^5+x^4-4*x^3-3*x^2+3*x+1);
#I  Partitions Test
#I  cands:[ 1, 2, 4 ]
#I  2-Set Resolvent
#I  trying res nr. 0
#I  SumRootsPol 2
#I  Candidates :[ 1, 2 ]
#I  2-Seq Resolvent
#I  TwoSeqPol 2
#I  Candidates :[ 1 ]
1

here cycle shapes leave groups 1,2 and 4 left. Action on 2-sets (SumRootsPol 2) leaves 1 and 2, and 2-sequences finally nails the group.
If you do this on $x^3+x^2-2x-1$ above you notice that the 2-sequence polynomial is never used. That is because we can distinguish $A_n$/$S_n$ by whether the discriminant (for $p$ it is $49$) is a square.
