36 #include <permlib/generator/product_replacement_generator.h> 37 #include <permlib/transversal/explicit_transversal.h> 38 #include <permlib/bsgs.h> 39 #include <permlib/construct/schreier_sims_construction.h> 40 #include <permlib/prime_helper.h> 42 #include <boost/foreach.hpp> 43 #include <boost/math/common_factor_rt.hpp> 60 template<
typename PERM>
76 template<
typename ForwardIterator,
typename TRANS>
91 template<
typename ForwardIterator>
95 return determineGiantType<ForwardIterator, TRANS>(eps, n, begin, end, bsgs, isKnownPrimitive);
105 template<
typename ForwardIterator>
110 static GiantGroupType giantTypeByOrder(
const T& order,
const T& symOrder);
114 template<
typename PERM>
115 template<
typename ForwardIterator>
117 typedef std::pair<dom_int, unsigned int> CyclePair;
118 for (ForwardIterator pit = begin; pit != end; ++pit) {
119 unsigned int parity = 0;
120 std::list<CyclePair> genCycles = (*pit)->cycles();
121 BOOST_FOREACH(
const CyclePair& c, genCycles) {
122 if (c.second % 2 == 0)
131 template<
typename PERM>
134 if (order == symOrder / 2)
136 if (order == symOrder)
141 template<
typename PERM>
142 template<
typename ForwardIterator,
typename TRANS>
149 for (ForwardIterator pit = begin; pit != end; ++pit) {
150 if ( ! (*pit)->isIdentity() )
155 SchreierSimsConstruction<PERM, TRANS> ssc(n);
156 bsgs = ssc.construct(begin, end);
157 const boost::uint64_t order = bsgs.order();
160 return giantTypeByOrder(order, static_cast<boost::uint64_t>(6));
162 return giantTypeByOrder(order, static_cast<boost::uint64_t>(24));
164 return giantTypeByOrder(order, static_cast<boost::uint64_t>(120));
166 return giantTypeByOrder(order, static_cast<boost::uint64_t>(720));
168 return giantTypeByOrder(order, static_cast<boost::uint64_t>(5040));
177 const unsigned int randomRuns =
static_cast<unsigned int>(-std::log(eps) * std::log(n) / 0.395);
179 ProductReplacementGenerator<PERM> rng(n, begin, end);
180 for (
unsigned int i = 0; i < randomRuns; ++i) {
181 PERM randPerm = rng.next();
182 typedef std::pair<dom_int, unsigned int> CyclePair;
183 std::list<CyclePair> cycleList = randPerm.cycles();
184 std::vector<unsigned int> cycleLength(cycleList.size());
186 BOOST_FOREACH(
const CyclePair& c, cycleList) {
187 cycleLength[j++] = c.second;
189 for (j = 0; j < cycleLength.size(); ++j) {
190 const unsigned int len = cycleLength[j];
194 bool isCoprime =
true;
195 for (
unsigned int k = 0; k < cycleLength.size(); ++k) {
198 if (boost::math::gcd(cycleLength[j], cycleLength[k]) != 1) {
206 if (isSubgroupOfAlternatingGroup(begin, end))
Definition: giant_test.h:50
GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS< PERM, TRANS > &bsgs, bool isKnownPrimitive=false) const
tests whether group given by generators is an Alternating or a Symmetric Group
Transversal class that stores all transversal elements explicitly.
Definition: explicit_transversal.h:42
Tests a group given by generators for being an Alternating Group or a Symmetric Group.
Definition: giant_test.h:61
static bool isPrimeNumber(unsigned int x, bool checkBounds)
checks if a given number is prime
Definition: prime_helper.h:52
GiantGroupType
Enumeration of "giant" groups, i.e. Alternating and Symmetric group.
Definition: giant_test.h:52
static bool isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end)
tests whether group given by generators is a subgroup of an Alternating Group
Definition: giant_test.h:116
GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, bool isKnownPrimitive=false) const
tests whether group given by generators is an Alternating or a Symmetric Group
Definition: giant_test.h:92
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
Definition: abstract_bsgs.h:49