Как построить большое простое число | Журнал Кванта

Простые числа — сложная штука. В школе мы узнаем, что это числа, у которых нет других делителей, кроме 1 и самих себя, и что математикам уже тысячи лет известно, что их существует бесконечное множество. Создание одного по команде не кажется трудным.

Но это. Построение произвольно больших простых чисел чрезвычайно сложно. По сути, у вас есть два вычислительных варианта, оба с недостатками. Вы можете использовать случайность и найти его путем угадывания, но этот метод непостоянен — вы рискуете каждый раз генерировать новое простое число. Или вы можете использовать более надежный детерминированный алгоритм, но с большими вычислительными затратами.

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

«Они изложили последовательность попыток, каждая из которых пыталась построить простое число разной длины, и показали, что одна из попыток работает», — сказал Рои Телль, ученый-теоретик из Института перспективных исследований, не участвовавший в этой работе. «Это конструкция, которая выводит детерминистически выбранное простое число, но позволяет вам подбрасывать монеты и делать случайный выбор в процессе».

Проблема создания эффективного рецепта простых чисел имеет глубокие корни. «На самом деле мы мало что знаем о том, как распределяются простые числа, или о промежутках между простыми числами», — сказал Офер Гроссман, изучающий псевдослучайные алгоритмы. И если мы не знаем, где их найти, нет простого способа сгенерировать простое число с нуля.

Со временем исследователи разработали вышеупомянутые подходы. Самый простой способ — просто угадать. Например, если вам нужно простое число с 1,000 цифрами, вы можете выбрать случайным образом 1,000-значное число, а затем проверить его. «Если это не простое число, вы просто пробуете еще одно, другое и так далее, пока не найдете одно», — сказал он. Рахул Сантанам, ученый-компьютерщик из Оксфордского университета и соавтор новой статьи. «Поскольку существует много простых чисел, этот алгоритм даст вам некоторое число, которое является простым с высокой вероятностью, после относительно небольшого количества итераций». Но использование случайности означает, что вы, вероятно, каждый раз будете получать разные числа, сказал он. Это может быть проблемой, если вам нужна согласованность — если, скажем, вы используете криптографический метод защиты, зависящий от наличия больших простых чисел.

Другой подход заключается в использовании детерминированного алгоритма. Вы можете выбрать отправную точку и начать последовательно проверять числа на простоту. В конце концов вам суждено найти его, и ваш алгоритм будет последовательно выводить первое найденное вами. Но это может занять некоторое время: если вы ищете простое число с 1,000 цифр, даже вычисление с 2⁵⁰⁰ шагов — которые заняли бы гораздо больше времени, чем возраст Вселенной — недостаточно, чтобы гарантировать успех.

В 2009 году математик и медалист Филдса Теренс Тао хотел добиться большего. Он призвал математиков придумать детерминированный алгоритм для нахождения простого числа заданного размера в пределах вычислительного времени.

Этот предел времени известен как полиномиальное время. Алгоритм решает задачу за полиномиальное время, если количество шагов, которые он выполняет, не превышает полиномиальной функции от n, размер ввода. (Полиномиальная функция включает члены, переменные которых возведены в положительные целые степени, например n² или 4n³.) В контексте построения простых чисел n относится к количеству цифр в простом, которое вы хотите. С вычислительной точки зрения это не требует больших затрат: ученые-компьютерщики описывают проблемы, которые могут быть решены с помощью алгоритмов за полиномиальное время, как простые. Сложная задача, напротив, требует экспоненциального времени, что означает, что она требует ряда шагов, аппроксимируемых экспоненциальной функцией (которая включает такие термины, как 2ⁿ).

На протяжении десятилетий исследователи исследовали связь между случайностью и жесткостью. Задача построения простых чисел считалась легкой, если вы допускали случайность — и каждый раз удовлетворялись получением другого числа — и сложной, если вы настаивали на детерминизме.

Пока еще никому не удалось ответить на вызов Тао, но новая работа приближается. Он в значительной степени опирается на подход, предложенный в 2011 году Шафи Голдвассером и Эраном Гатом, учеными-компьютерщиками из Массачусетского технологического института. Они описали «псевдодетерминированные» алгоритмы — математические рецепты задач поиска, таких как поиск больших простых чисел, которые могли бы использовать преимущества случайности и с высокой вероятностью по-прежнему каждый раз давать один и тот же ответ. Они будут использовать эффективность случайных битов в рецепте, который будет дерандомизирован в результате, что будет казаться детерминированным.

С тех пор исследователи изучают псевдодетерминированные алгоритмы. В 2017 году Сантанам и Игорь Оливейра из Уорикского университета (которые также внесли свой вклад в новую работу) описано псевдодетерминированный подход к построению простых чисел, который использовал случайность и выглядел убедительно детерминированным, но работал в «субэкспоненциальном» времени — быстрее, чем экспоненциальное, но медленнее, чем полиномиальное время. Затем в 2021 году Телль и Лицзе Ченученый-компьютерщик Калифорнийского университета в Беркли. его начали использовать как использовать сложную задачу для создания генератора псевдослучайных чисел (алгоритм, который генерирует строку чисел, неотличимую от случайного вывода). «[Мы] обнаружили новую связь между жесткостью и псевдослучайностью», — сказал Чен.

Части наконец сошлись воедино весной 2023 года, во время буткемп по вычислительной сложности в Институте теории вычислений Саймонса в Беркли, когда исследователи начали вместе работать над проблемой, объединяя прошлые результаты. Чен сказал, что для новой работы Ханлин Рен — ученый-компьютерщик из Оксфорда и соавтор — предложил первоначальные идеи по новому сочетанию результата Чена-Телла с подходом Сантанам-Оливейра. Затем вся команда более полно разработала идеи для создания новой статьи.

Получившийся в результате псевдодетерминированный алгоритм, по словам Сантанама, использовал новые способы рассмотрения прошлой работы для получения простых чисел за полиномиальное время. Доказано, что он использовал случайность для вывода простого числа определенной длины, и этот инструмент более точен, чем случайное угадывание, и более эффективен в вычислительном отношении, чем детерминистический анализ.

По словам Сантанама, новый алгоритм удивительно прост, и его можно применять к широкому кругу задач поиска — на самом деле, к любому плотному подмножеству чисел, например, к простым числам, принадлежность которых можно определить за полиномиальное время. Но это не идеально. Алгоритм работает для бесконечного множества входных длин, но не охватывает все длины цифр. Там могут быть еще некоторые значения n там, для которых алгоритм не детерминистически производит простое число.

«Было бы здорово избавиться от этой маленькой оговорки», — сказал Гроссман.

Конечная цель, по словам Сантанама, — найти алгоритм, который вообще не требует случайности. Но этот квест остается открытым. «Детерминизм — это то, что мы хотели бы использовать», — сказал он.

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

«Интересно попытаться подумать, к чему еще приведут эти блестящие наблюдения, — сказал Телль.