Fast constructive recognition of a black box group isomorphic to Sn or An using Goldbach's Conjecture

The well-known Goldbach Conjecture (GC) states that any sufficiently large even number can be represented as a sum of two odd primes. Although not yet demonstrated, it has been checked for integers up to 10(14) . Using two stronger versions of the conjecture, we offer a simple and fast method for recognition of a gray box group G known to be isomorphic to S-n (or A(n)) with known n greater than or equal to 20, i.e. for construction(dagger) of an isomorphism from G to S-n (or A(n)). Correctness and rigorous worst case complexity estimates rely heavily on the conjectures, and yield times of O([rho+nu+eta] n log(2) n) or O([rho+nu+mu] n log n/log log n) depending on which of the stronger versions of the GC is assumed to hold. Here, rho is the complexity of generating a uniform random element of G, nu is the complexity of finding the order of a group element in G, and mu is the time necessary for group multiplication in G. Rigorous lower bound and probabilistic approach to the time complexity of the algorithm are discussed in the Appendix. (C) 2000 Academic Press.