33 #ifndef PRODUCTREPLACEMENTGENERATOR_H 34 #define PRODUCTREPLACEMENTGENERATOR_H 36 #include <permlib/generator/random_generator.h> 39 #include <boost/iterator/indirect_iterator.hpp> 52 template <
class InputIterator>
57 std::vector<PERM> m_generators;
58 const unsigned int m_n;
66 template <
class InputIterator>
68 : m_generators(boost::indirect_iterator<InputIterator, PERM>(generatorsBegin),
69 boost::indirect_iterator<InputIterator, PERM>(generatorsEnd)),
72 const unsigned int additionalElements = 10;
73 const unsigned int oldSize = m_generators.size();
74 const unsigned int replacementRounds = std::max(oldSize * 10, static_cast<unsigned int>(100));
78 m_generators.reserve(oldSize + additionalElements + 1);
79 for (
unsigned int i = 0; i < additionalElements; ++i) {
80 m_generators.push_back(m_generators[randomInt(oldSize)]);
82 m_generators.push_back(PERM(m_generators[0].size()));
84 for (
unsigned int k = 0; k < replacementRounds; ++k) {
91 if (m_generators.size() == 0) {
95 unsigned int i = randomInt(m_generators.size() - 1);
96 unsigned int j = randomInt(m_generators.size() - 2);
98 switch (randomInt(4)) {
100 m_generators[i] *= m_generators[j];
break;
102 m_generators[i] *= ~m_generators[j];
break;
104 m_generators[i] ^= m_generators[j];
break;
106 m_generators[i] ^= ~m_generators[j];
break;
108 m_generators[m_generators.size()-1] *= m_generators[i];
109 return m_generators[m_generators.size()-1];
114 #endif // -- PRODUCTREPLACEMENTGENERATOR_H ProductReplacementGenerator(const unsigned int n, InputIterator generatorsBegin, InputIterator generatorsEnd)
initializes class with group generators
Definition: product_replacement_generator.h:67
abstract base class for random group element generators
Definition: random_generator.h:42
virtual PERM next()
generates an element
Definition: product_replacement_generator.h:90
generates nearly-uniformly distributed random group elements using the product replacement algorithm ...
Definition: product_replacement_generator.h:45
Definition: abstract_bsgs.h:49