- PVSM.RU - https://www.pvsm.ru -

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти - 1
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский [1] придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена [2].

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.

В виде алгоритма решето Эратосфена формализуется следующим образом:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
  4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4, пока возможно.

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти - 2

После выполнения этой операции незачёркнутыми в списке остаются только простые числа.

Очевидно, что компьютерная реализация решета Эратосфена требует большого объёма памяти. Так оно и было, пока своё решение [3] проблемы не предложил 38-летний перуанский математик Харальд Хельфготт [4].

Харальд Хельфготт

Харальд Хельфготт привлёк всеобщее внимание в 2013 году, когда ему удалось решить тернарную проблему Гольдбаха [5]. Тернарная проблема Гольдбаха — более слабое утверждение основной бинарной проблемы Гольдбаха [6] — одной из самых известных открытых математических проблем, которая до сих пор остаётся нерешённой. Это утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.

Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от 1 до N Иваном Виноградовым [7] в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что граница N в работе Виноградова составляет всего лишь 106 846 168.

Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу — уже действительно для всех чисел. Его доказательство опубликовано [8] в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао [9].

Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки — оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена — метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется.

«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит [3] Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.

Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.

Специалисты говорят, что эффективность алгоритма определяется двумя факторами:

  1. Количество операций на один бит входных данных.
  2. Количество бит в памяти во время выполнения инструкций.

По количеству операций на бит решётка Эратосфена относительно эффективна. Оно растёт пропорционально размеру интервала от 1 до N. А вот если посмотреть, что нужно хранить в памяти для каждого шага алгоритма на больших интервалах, то ни о какой эффективности не идёт и речи.

Оптимизация решета Эратосфена

Для оптимизации компьютерного алгоритма решета Эратосфена математик применил вариант того же метода, который использовал при работе над тернарной проблемой Гольдбаха. Речь идёт о круговом методе Харди-Литтлвуда [10]. Том самом методе, который в начале прошлого века великолепно усовершенствовал математик Иван Виноградов, в результате чего почти сумел доказать гипотезу Гольдбаха.

Согласно методу Харди-Литтлвуда, решение задачи задаётся интегралом по единичной окружности от некоторого ряда. Этот интеграл разбивается на два, один из которых оценивается, а про другой доказывается его относительная малость. Составляющие первую сумму называются большими дугами, а вторую — малыми.

Сам математик объясняет [11] метод следующим образом:

«Анализ количества решений производится, по сути, посредством преобразования Фурье [12]. Представьте себе, что простые числа — это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, — это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, — это малые дуги. Весь метод распадается на две части — выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй — на малые».

На основе метода Харди-Литтлвуда учёный разработал подход, который позволяет вместо объёма оперативной памяти N использовать объём памяти ∛N (кубический корень из N).

Образно говоря, вместо 1 гигабайта памяти, т.е. 109 байт (не путать с гибибайтом 230) нужен всего лишь 1 мегабайт (∛109 = 103 байт).

Гигабайт и мегабайт — большая разница, согласитесь.

Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.

Тезисы своей работы Харальд Хельфготт представил на 21-м Латиноамериканском коллоквиуме по алгебре [13] в Буэнос-Айресе 25-29 июля 2016 года, а также на мероприятии Sinapsis 2016 в Париже — неформальной встрече перуанских учёных, проживающих в Европе.

Есть разные алгоритмы для поиска простых чисел, но Хельфготт обращает внимание, что решето Эратосфена имеет важное качество — оно совместимо с другими математическими операциями, такими как факторизация, а ведь именно на факторизации (разложении больших простых чисел на множители) базируется криптография. «Факторизация стала ключевым элементом современной цивилизации», — констатирует Хельфготт.

Автор: alizar

Источник [14]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/nauchno-populyarnoe/193146

Ссылки в тексте:

[1] Эратосфен Киренский: https://ru.wikipedia.org/wiki/Эратосфен

[2] решето Эратосфена: https://ru.wikipedia.org/wiki/Решето_Эратосфена

[3] своё решение: http://www.scientificamerican.com/article/new-take-on-an-ancient-method-improves-way-to-find-prime-numbers/

[4] Харальд Хельфготт: https://ru.wikipedia.org/wiki/Хельфготт,_Харальд

[5] тернарную проблему Гольдбаха: https://ru.wikipedia.org/wiki/Проблема_Гольдбаха#.D0.A2.D0.B5.D1.80.D0.BD.D0.B0.D1.80.D0.BD.D0.B0.D1.8F_.D0.BF.D1.80.D0.BE.D0.B1.D0.BB.D0.B5.D0.BC.D0.B0_.D0.93.D0.BE.D0.BB.D1.8C.D0.B4.D0.B1.D0.B0.D1.85.D0.B0

[6] бинарной проблемы Гольдбаха: https://ru.wikipedia.org/wiki/Проблема_Гольдбаха

[7] Иваном Виноградовым: https://ru.wikipedia.org/wiki/Виноградов,_Иван_Матвеевич

[8] опубликовано: http://science.sciencemag.org/content/340/6135/913.summary

[9] Теренсом Тао: https://plus.google.com/+TerenceTao27/posts/8qpSYNZFbzC

[10] круговом методе Харди-Литтлвуда: https://en.wikipedia.org/wiki/Hardy%E2%80%93Littlewood_circle_method

[11] объясняет: https://lenta.ru/articles/2013/06/17/goldbach/

[12] преобразования Фурье: https://ru.wikipedia.org/wiki/Преобразование_Фурье

[13] 21-м Латиноамериканском коллоквиуме по алгебре: http://cms.dm.uba.ar/actividades/congresos/XXICLA/index_e_html

[14] Источник: https://geektimes.ru/post/280896/