This document contains the mathematical foundations and references for the algorithms used in TrueEntropy.
- Entropy and Information Theory
- Cryptographic Primitives
- Random Number Generation
- Probability Distributions
- Statistical Tests
- External Sources
The entropy of a discrete random variable X is defined as:
H(X) = -Σ p(x) log₂ p(x)
References:
- Shannon, C. E. (1948). "A Mathematical Theory of Communication"
- https://en.wikipedia.org/wiki/Entropy_(information_theory)
Used for mixing entropy in the pool. Properties:
- Output: 256 bits (32 bytes)
- Collision resistance: 2^128 operations
- Preimage resistance: 2^256 operations
References:
- FIPS 180-4: Secure Hash Standard
- https://csrc.nist.gov/publications/detail/fips/180/4/final
A small change in input produces a completely different output:
P(bit_i changes | 1 bit input change) ≈ 0.5
Converting n random bits to float in [0, 1):
float_value = integer_value / 2^n
We use 64 bits for maximum precision (~15-17 significant decimal digits).
To generate uniform integer in [a, b]:
range = b - a + 1
bits_needed = ceil(log₂(range))
mask = 2^bits_needed - 1
repeat:
raw = extract_bits(bits_needed)
value = raw & mask
until value < range
return a + value
Why rejection sampling? Simple modulo causes bias when range doesn't divide 2^n evenly.
References:
For uniform random permutation:
for i from n-1 down to 1:
j = random_int(0, i)
swap(arr[i], arr[j])
References:
- Fisher, R.A.; Yates, F. (1938). "Statistical Tables"
- https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Using Box-Muller transform:
Z₀ = √(-2 ln U₁) cos(2π U₂)
Z₁ = √(-2 ln U₁) sin(2π U₂)
Where U₁, U₂ ~ Uniform(0, 1)
References:
- Box, G. E. P.; Muller, M. E. (1958)
- https://www.statisticshowto.com/box-muller-transform-simple-definition/
- https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform
Using inverse transform:
X = -ln(U) / λ
Where U ~ Uniform(0, 1), λ is rate parameter
References:
if U < (mode - low) / (high - low):
X = low + √(U × (high - low) × (mode - low))
else:
X = high - √((1-U) × (high - low) × (high - mode))
References:
Cumulative distribution method:
total = sum(weights)
threshold = random() * total
cumulative = 0
for i, weight in enumerate(weights):
cumulative += weight
if threshold < cumulative:
return items[i]
For testing uniformity:
χ² = Σ (O_i - E_i)² / E_i
Where O_i = observed frequency, E_i = expected frequency
Statistical test suite for random number generators:
- Frequency (monobit) test
- Block frequency test
- Runs test
- Longest run test
- etc.
References:
| Source | Entropy Quality | Notes |
|---|---|---|
| CPU Timing Jitter | Medium | OS scheduler, cache effects |
| Network Latency | Medium | Congestion, routing variability |
| System State | Low-Medium | Volatile but somewhat predictable |
| Weather APIs | Medium | Chaotic atmospheric systems |
| random.org | High | Atmospheric noise, quantum effects |
| ANU QRNG | Very High | Quantum vacuum fluctuations |
xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx
Where:
- x = random hex digit
- 4 = version (always 4 for random UUID)
- y = variant (8, 9, a, or b)
References:
- RFC 4122: https://tools.ietf.org/html/rfc4122
Add your mathematical references here following the format:
### Topic Name
Formula or algorithm description:
\`\`\`
mathematical_notation_here
\`\`\`
**References:**
- Author (Year). "Title"
- URLGuilherme de Medeiros - UNICAMP
