## Abstract

An (n,k)-affine source over a finite field F is a random variable X = (X _{1},..., X _{n} ) ε Fn which is uniformly distributed over an (unknown) k-dimensional affine subspace of Fn . We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than n ^{c} (where c is a large enough constant). Our main results are as follows: 1. (For arbitrary k): For any n,k and any F of size larger than n ^{20}, we give an explicit construction for a function D Fn → Fk - 1, such that for any (n,k)-affine source X over F, the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. 2. (For k=1): For any n and any F of size larger than n ^{c} , we give an explicit construction for a function D: Fn \to \{ 0,1\} {(1 - \delta )log-2 |F| , such that for any (n, 1)-affine source X over F , the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. Here, δ>0 is an arbitrary small constant, and c is a constant depending on δ.

Original language | English (US) |
---|---|

Pages (from-to) | 415-440 |

Number of pages | 26 |

Journal | Combinatorica |

Volume | 28 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2008 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics