#!/usr/bin/python

# For simplicity, we fix domain and range of PRGs here:
# The domain is the set of 32-bit integers
# The random is the set of ten-element lists of 32-bit integers
#   (equivalent to 320-bit integers)

import random

# A very bad pseudo-random generator
# Seed is supposed to be a 32-bit integer
# Output is a ten element list of 32-bit integers
def G(seed):
    return [4267243**i*seed % 2**32 for i in range(1,11)]

# The game: it gets a prg and an adversary as arguments
def prg_game(G,adv):
    b = random.randint(0,1) # Random bit
    seed = random.randint(0,2**32-1) # Random seed
    rand = [random.randint(0,2**32-1) for i in range(10)] # Truly random output
    if b==0: badv = adv(G(seed))
    else: badv = adv(rand)
    return b==badv
        
def adv(rand):
    if rand[1]==4267243*rand[0] % 2**32: return 0
    else: return 1

def test_prg(G,adv):
    num_true = 0
    num_tries = 100000
    for i in range(num_tries):
        if prg_game(G,adv): num_true += 1
    ratio = float(num_true)/num_tries
    print ratio

# An output near 0.5 means no attack
# An output neat 0.0 or 1.0 means a successful attack
test_prg(G,adv)