Псевдослучайные генераторы многочленов - Pseudorandom generators for polynomials - Wikipedia

В теоретическая информатика, а псевдослучайный генератор полиномов низкой степени является эффективной процедурой, которая отображает короткое истинно случайное начальное число в более длинную псевдослучайную строку таким образом, что полиномы низкой степени не могут отличить выходное распределение генератора от истинно случайного распределения. Таким образом, оценка любого полинома низкой степени в точке, определенной псевдослучайной строкой, статистически близка к оценке того же полинома в точке, которая выбирается равномерно случайным образом.

Псевдослучайные генераторы для полиномов низкой степени являются частным примером псевдослучайные генераторы для статистических тестов, где рассматриваемые статистические тесты являются оценками многочленов низкой степени.

Определение

Псевдослучайный генератор ${\displaystyle G:\mathbb {F} ^{\ell }\rightarrow \mathbb {F} ^{n}}$ для многочленов степени ${\displaystyle d}$ через конечное поле ${\displaystyle \mathbb {F} }$ эффективная процедура, отображающая последовательность ${\displaystyle \ell }$ элементы поля в последовательность ${\displaystyle n}$ элементы поля такие, что любые ${\displaystyle n}$-переменный полином над ${\displaystyle \mathbb {F} }$ степени ${\displaystyle d}$ вводится в заблуждение выходным распределением ${\displaystyle G}$Другими словами, для каждого такого многочлена ${\displaystyle p(x_{1},\dots ,x_{n})}$, то статистическое расстояние между раздачами ${\displaystyle p(U_{n})}$ и ${\displaystyle p(G(U_{\ell }))}$ это в лучшем случае небольшой ${\displaystyle \epsilon }$, куда ${\displaystyle U_{k}}$ равномерное распределение по ${\displaystyle \mathbb {F} ^{k}}$.

Строительство

Ловетт (третий слева) в 2009 году

Дело ${\displaystyle d=1}$ соответствует псевдослучайные генераторы линейных функций и решается генераторы малого смещения Например, построение Наор и Наор (1990) достигает длины семян ${\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}$, что оптимально с точностью до постоянных факторов.

Богданов и Виола (2007) предположили, что сумма генераторов малого смещения обманывает многочлены низкой степени, и смогли доказать это при Обратная гипотеза Гауэрса.Ловетт (2009) безоговорочно доказано, что сумма ${\displaystyle 2^{d}}$ пространства малого смещения обманывают многочлены степени ${\displaystyle d}$.Альт (2008) доказывает, что на самом деле, если взять сумму только ${\displaystyle d}$ генераторов малого смещения достаточно, чтобы обмануть многочлены степени ${\displaystyle d}$.Анализ Альт (2008) дает длину семени ${\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}$.

Рекомендации

• Богданов, Андрей; Альт, Эмануэле (2007), «Псевдослучайные биты для многочленов», Материалы 48-го ежегодного симпозиума по основам компьютерных наук (FOCS 2007): 41–51, Дои:10.1109 / FOCS.2007.56, ISBN  978-0-7695-3010-9
• Ловетт, Шахар (2009), "Безусловные псевдослучайные генераторы для многочленов низкой степени", Теория вычислений, 5 (3): 69–82, Дои:10.4086 / toc.2009.v005a003
• Наор, Иосиф; Наор, Мони (1990), "Пространства вероятностей малого смещения: эффективные конструкции и приложения", Материалы 22-го ежегодного симпозиума ACM по теории вычислений, STOC 1990: 213–223, CiteSeerX  10.1.1.421.2784, Дои:10.1145/100216.100244, ISBN  978-0897913614
• Альт, Эмануэле (2008), "Сумма d генераторов малого смещения обманывает многочлены степени d" (PDF), Труды 23-й ежегодной конференции по вычислительной сложности (CCC 2008): 124–127, CiteSeerX  10.1.1.220.1554, Дои:10.1109 / CCC.2008.16, ISBN  978-0-7695-3169-4