Генераторы псевдослучайных чисел для многочленов - Википедия - Pseudorandom generators for polynomials

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

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

Определение

Псевдослучайный генератор ${ 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 = журнал п + О ( журнал ( эпсилон ^ {- 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-9CS1 maint: ref = harv (связь)
• Ловетт, Шахар (2009), "Безусловные псевдослучайные генераторы для многочленов низкой степени", Теория вычислений, 5 (3): 69–82, Дои:10.4086 / toc.2009.v005a003CS1 maint: ref = harv (связь)
• Наор, Иосиф; Наор, Мони (1990), "Пространства вероятностей малого смещения: эффективные конструкции и приложения", Материалы 22-го ежегодного симпозиума ACM по теории вычислений, STOC 1990: 213–223, CiteSeerX  10.1.1.421.2784, Дои:10.1145/100216.100244, ISBN  978-0897913614CS1 maint: ref = harv (связь)
• Альт, Эмануэле (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-4CS1 maint: ref = harv (связь)