prng_1.py

from ecff.finitefield.finitefield import FiniteField

class prng:
    def __init__(self,n=104729,seed=42):
        """
        create a new prng using a finite field
        of order n. n must be prime, as we basically
        use the integers mod some prime (Z mod p).
        Jeremy Kun's code lets us make this actual
        arithmetic code quite nice. We do take a
        performance hit, but not a *ton*

        n: order of field (PICK A PRIME!!!)
        seed: initial state of RNG

        note that a seed of 88993 w/ default order
        gives an early repeated value. here there be pitfalls
        """
        self.group = FiniteField(n,1) #guarantees we use integers mod p
        #TODO: perhaps dynamically pick p and q?
        self.state = self.group(seed)
        self.P = self.group(7)
        self.Q = self.group(2)

    def get_num(self):
        """
        produce a number, and update our
        internal state

        try to copy the EC_DRBG algorithm

        THIS IS SUPER BROKEN. --- why did I comment this?
        TODO: review algorithm and see if it's super broken
        """
        #TODO: review which version of DUAL_EC_DRBG I was trying
        # to copy here, and if I did so correctly
        r = self.state * self.P
        self.state = r * self.P
        t = r * self.Q
        return t.n #define SO LONG AS we're in integers mod P

    def find_repeat(self):
        """
        UTILITY/TEST FUNCTION

        get random numbers until we receive a 
        number which we've already seen.

        In this algorithm, we essentially are 
        generating output based on a coset of 
        the subgroup generated by P**2, so once
        we repeat an output, we've started to
        loop over again.
        """
        vals = {}
        output = self.get_num()
        while output not in vals:
            vals[output] = self.get_num()
            output = vals[output]
        return len(vals)

    def test_output(self):
        """
        UTILITY/TEST FUNCTION

        Given the default finite field
        of order 104729, we almost always
        observe a cycle of 26182 elements.

        get this many random numbers, and see
        which are most frequent
        """
        vals = {}
        #found experimentally for default order
        for i in range(26182):
            key = self.get_num()
            if key in vals:
                vals[key]+=1
            else:
                vals[key]=1
        sorted_vals = sorted(vals.items(), key=lambda x:x[1], reverse=True)
        top_ten = sorted_vals[:10]
        print("top 10: ",top_ten)
        bottom_ten = sorted_vals[-10:]
        bottom_ten.reverse()
        print("bottom 10: ",bottom_ten)
        """
        gives WAAAY too much output if we use integers mod p
        without a mask

        for i in range(len(sorted_vals)-1):
            if sorted_vals[i+1] < sorted_vals[i]:
                print("break: ",i,", ",sorted_vals[i:i+2])
        """