A permutation generator built on the mathematics of finite fields

FiniteFieldShuffler.cs

using System;
using System.Collections;

namespace FiniteFieldShuffle
{
    /// <summary>
    /// Program to demonstrate an algorithm that generates a permutation of the values 0 through some
    /// maximum value using finite fields.
    /// </summary>
    public static class Program
    {
        [STAThread]
        static void Main()
        {
            SimpleDemo();

            FindPrimitiveElementsDemo();
        }

        private static void SimpleDemo()
        {
            FiniteFieldShuffler shuffler = new FiniteFieldShuffler(
                seed: 0,
                maxValue: 100,
                prime: 109,
                primitiveElement: 6
            );

            for( int i = 0; i < 1234; i++ )
            {
                Console.WriteLine( shuffler.GetNext() );
            }
        }

        private static void FindPrimitiveElementsDemo()
        {
            int prime = 109;

            for( int i = 0; i < prime; i++ )
            {
                if( FiniteFieldShuffler.TestPrimitiveElement( prime, i ) )
                {
                    TestGenerator( 0, 100, prime, i );
                }
            }
        }

        private static void TestGenerator( int seed, int maxValue, int prime, int primitiveElement )
        {
            BitArray found = new BitArray( maxValue + 1, false );

            var gen = new FiniteFieldShuffler( seed, maxValue, prime, primitiveElement );

            for( int i = 0; i <= maxValue; i++ )
            {
                found[gen.GetNext()] = true;
            }

            for( int i = 0; i < found.Count; i++ )
            {
                if( found[i] == false )
                {
                    throw new Exception();
                }
            }
        }

        /// <summary>
        /// Generates a permutation of values from 0 to some given maximum value N using the mathematics of finite fields.
        /// </summary>
        /// <remarks>
        /// Given a finite field of the form GF(p) where p is prime, it's possible to index all
        /// elements of the field, except for zero, by the power of some primitive element 'a' of the field.
        ///
        /// For instance, the field 'GF(5)' has the elements {0, 1, 2, 3, 4}. The same field could
        /// also be written, in a different order, as {0, a^0, a^1, a^2, a^3}, given some primitive
        /// element 'a'.
        ///
        /// For example, consider the following field:
        /// - p = 5
        /// - Addition: z = (x + y) mod p
        /// - Multiplication: z = (x * y) mod p
        /// - a = 2
        ///
        /// The following value are generated by the powers of the primitive element 'a':
        /// - a^0 mod 5 = 1 mod 5 = 1
        /// - a^1 mod 5 = 2 mod 5 = 2
        /// - a^2 mod 5 = 4 mod 5 = 4
        /// - a^3 mod 5 = 8 mod 5 = 3
        ///
        /// So the elements of GF(5) (defined using modulus and a = 2) could be written:
        /// - {0, a^0, a^1, a^2, a^3 }
        /// - {0, 1, 2, 4, 3 }
        ///
        /// Every value is generated once and only once per cycle.
        ///
        /// This random number generator stores the power of 'a' as its state, and returns the value
        /// of `a^i - 1`, for successive values of i.
        /// </remarks>
        public class FiniteFieldShuffler
        {
            private int value;
            private int maxValue;
            private int prime;
            private int primitiveElement;

            /// <summary>
            /// Initializes a new instance of the FiniteFieldShuffler class.
            /// </summary>
            /// <param name="seed">Specifies a seed value for the shuffler.</param>
            /// <param name="maxValue">Specifies the maximum value for the shuffler.</param>
            /// <param name="prime">
            /// Specifies the prime value used to define the underlying finite field.
            /// </param>
            /// <param name="primitiveElement">
            /// Specifies the primitive element used to define the underlying finite field.
            /// </param>
            /// <remarks>
            /// To discover primitive elements of a finite field given some prime, use <see
            /// cref="TestPrimitiveElement(int, int)"/>.
            ///
            /// The prime must be chosen such that it is at least 'maxValue + 2'.
            ///
            /// The prime should be chosen to be close to the maximum value. The underlying finite
            /// field has the same number of elements as the prime value; to restrain the returned
            /// values, the algorithm iteratively skips elements of the finite field greater than the
            /// maximum value as they are encountered.
            /// </remarks>
            public FiniteFieldShuffler( int seed, int maxValue, int prime, int primitiveElement )
            {
                if( maxValue > prime - 2 )
                {
                    throw new ArgumentException( "Must use a prime that is at least 'maxValue + 2'." );
                }

                this.maxValue = maxValue;
                this.prime = prime;
                this.primitiveElement = primitiveElement;

                this.value = primitiveElement;

                seed = seed % prime;

                for( int i = 0; i < seed; i++ )
                {
                    GetNext();
                }
            }

            /// <summary>
            /// Returns the next value in the permutation sequence.
            /// </summary>
            /// <returns></returns>
            public int GetNext()
            {
                // Computes the next value in the sequnce by computing the next power of the
                // primitive element as defined by the field.
                //
                // Skip over elements of the finite field that are larger than the requested max
                // value. Since no power of the primitive element is ever equal to zero, we handle
                // returning zero by increasing the max value by one, then subtracting by one to
                // shift the entire range down.
                do
                {
                    value = ( value * primitiveElement ) % prime;
                }
                while( value > maxValue + 1 );

                return value - 1;
            }

            public static bool TestPrimitiveElement( int prime, int candidateElement )
            {
                if( candidateElement >= prime )
                {
                    return false;
                }

                BitArray elements = new BitArray( prime, false );

                int value = candidateElement;

                elements[0] = true;
                elements[1] = true;

                for( int i = 1; i < prime; i++ )
                {
                    elements[value] = true;

                    value = ( value * candidateElement ) % prime;
                }

                for( int i = 0; i < elements.Count; i++ )
                {
                    if( elements[i] == false )
                    {
                        return false;
                    }
                }

                return true;
            }
        }
    }
}

For some more information on computing over finite fields, see the comments in this file:

https://github.com/antiduh/ErrorCorrection/blob/master/ErrorCorrection/GaloisField.cs