#!/usr/bin/python
# Juels, Jakobsson, Shriver, and Hillyer integer unbiaser version 1.0
# Convert a biased uncorrelated stream of integers (eg, click
# intervals from a Geiger counter) into an unbiased uncorrelated
# bitstream. See
# http://www.ciphergoth.org/software/unbiasing
import random
def factorial(n):
res = 1L
for i in range(1, n):
res = res * i
return res
def q_one(seq):
freq_hash = {}
for x in seq:
if freq_hash.has_key(x):
freq_hash[x] = freq_hash[x] +1
else:
freq_hash[x] = 1
rank_map = freq_hash.keys()
rank_map.sort()
ranks = len(rank_map)
fr = [freq_hash[x] for x in rank_map]
key_rank = {}
for (key, rank) in map(None, rank_map, range(0, ranks)):
key_rank[key] = rank
rseq = [key_rank[x] for x in seq]
little_n = len(rseq)
perms = factorial(little_n)
for f in fr:
perms = perms / factorial(f)
big_l = 0
big_f = perms
for (x,i) in map(None, rseq, range(0, little_n)):
little_l = 0
for r in range(0, x):
little_l = little_l + fr[r]
little_v = fr[x]
remaining = little_n - i
big_l = big_l + little_l * big_f / remaining
big_f = little_v * big_f / remaining
fr[x] = fr[x] -1
return (big_l, perms)
def q_two(r,s):
res = ""
while (s % 2 == 0 or r != s-1):
s_2 = s/2
if r % 2 == 1:
res = res + "1"
else:
res = res + "0"
r = r/2
s = s_2
return res
def extract_juice(seq):
(r, s) = q_one(seq)
return q_two(r, s)
n = 1
k = 1024
for i in range(0, n):
# Numbers from HotBits hbhist.gif
data = []
for j in range(0, k):
sample = int(0.5 + random.gauss(1889.35,26.4))
#sample = (sample * 1000) % 2011
data.append(sample)
bits = len(extract_juice(data))
print "Bits:", bits
print "Efficiency: ", bits * 1.0 / k
# Copyright (C) 2002 Paul Crowley
# November 2002
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.