38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matias Loewy
В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.
Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
В виде алгоритма решето Эратосфена формализуется следующим образом:
- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
- Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4, пока возможно.
После выполнения этой операции незачёркнутыми в списке остаются только простые числа.
Очевидно, что компьютерная реализация решета Эратосфена требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил 38-летний перуанский математик Харальд Хельфготт.
Харальд Хельфготт
Харальд Хельфготт привлёк всеобщее внимание в 2013 году, когда ему удалось решить тернарную проблему Гольдбаха. Тернарная проблема Гольдбаха — более слабое утверждение основной бинарной проблемы Гольдбаха — одной из самых известных открытых математических проблем, которая до сих пор остаётся нерешённой. Это утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.
Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от N до бесконечности Иваном Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что нижняя граница N в работе Виноградова составляет 106 846 168.
Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу, снизив границу N до приемлемого числа 1029, а все остальные числа проверили на суперкомпьютере. Его доказательство опубликовано в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао.
Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки — оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена — метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется.
«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.
Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.
Специалисты говорят, что эффективность алгоритма определяется двумя факторами:
- Количество операций на один бит входных данных.
- Количество бит в памяти во время выполнения инструкций.
По количеству операций на бит решётка Эратосфена относительно эффективна. Оно растёт пропорционально размеру интервала от 1 до N. А вот если посмотреть, что нужно хранить в памяти для каждого шага алгоритма на больших интервалах, то ни о какой эффективности не идёт и речи.
Оптимизация решета Эратосфена
Для оптимизации компьютерного алгоритма решета Эратосфена математик применил вариант того же метода, который использовал при работе над тернарной проблемой Гольдбаха. Речь идёт о круговом методе Харди-Литтлвуда. Том самом методе, который в начале прошлого века великолепно усовершенствовал математик Иван Виноградов, в результате чего почти сумел доказать гипотезу Гольдбаха.
Согласно методу Харди-Литтлвуда, решение задачи задаётся интегралом по единичной окружности от некоторого ряда. Этот интеграл разбивается на два, один из которых оценивается, а про другой доказывается его относительная малость. Составляющие первую сумму называются большими дугами, а вторую — малыми.
Сам математик объясняет метод следующим образом:
«Анализ количества решений производится, по сути, посредством преобразования Фурье. Представьте себе, что простые числа — это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, — это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, — это малые дуги. Весь метод распадается на две части — выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй — на малые».
На основе метода Харди-Литтлвуда учёный разработал подход, который позволяет вместо объёма оперативной памяти N использовать объём памяти ?N (кубический корень из N).
Образно говоря, вместо 1 гигабайта памяти, т.е. 109 байт (не путать с гибибайтом 230) нужен всего лишь 1 килобайт (?109 = 103 байт).
Гигабайт и килобайт — большая разница, согласитесь.
Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.
Тезисы своей работы Харальд Хельфготт представил на 21-м Латиноамериканском коллоквиуме по алгебре в Буэнос-Айресе 25-29 июля 2016 года, а также на мероприятии Sinapsis 2016 в Париже — неформальной встрече перуанских учёных, проживающих в Европе.
Есть разные алгоритмы для поиска простых чисел, но Хельфготт обращает внимание, что решето Эратосфена имеет важное качество — оно совместимо с другими математическими операциями, такими как факторизация, а ведь именно на факторизации (разложении больших чисел на простые множители) базируется криптография. «Факторизация стала ключевым элементом современной цивилизации», — констатирует Хельфготт.
Комментарии (50)
psylostlife
28.09.2016 00:46+19«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит Харальд Хельфготт
А вот сейчас обидненько было.batja84
28.09.2016 01:50Может он только перуанских детей имел в виду? Мало ли что они там в 4-5 классах по математике изучают. :)
Dmitry_Dor
28.09.2016 04:21+2А вот сейчас обидненько было
План-конспект урока (6 класс) по теме:
Конспект урока «Простые и составные числа. Решето Эратосфена»
avost
28.09.2016 07:49Только 6 класс — это 12 — 13 лет.
LeonidZ
28.09.2016 11:08Ну… у всех по-разному. Я 84-го года (конец августа), в 6-й класс пошел в 94-м году, ровно в 10 лет. Так что вполне человек может не врать. Я тоже в 10 лет проходит решето Эратосфена.
avost
28.09.2016 12:22-1В 5 лет в школу пошли? Это довольно редкое исключение из правил. Я в 3 года читать научился, но сказать «как и многие другие дети трёхлетнего возраста» было бы о-о-очень большим преувеличением :)
LeonidZ
28.09.2016 12:24+1Нет, почему же, в 6.
1990 (6 лет) — 1 класс
1991 (7 лет) — 2 класс
1992 (8 лет) — 3 класс
1993 (9 лет) — 5 класс
1994 (10 лет) — 6 класс
В гимназиях (и не только) в 90-х 4-й класс почти всегда перепрыгивали.avost
28.09.2016 13:30-3Тогда это не 6-й класс, а 5-й фактически. По ссылке нынешняя программа и по ней не перескакивают.
А вы точно помните, что именно в том году вы изучли «решето»? А то, вон, люди сверху считают, что это невозможно запомнить :)
Да, и 6 лет — тоже не правило, а исключение.LeonidZ
28.09.2016 13:38Точно не в 3-ем, поэтому точно в 5-ом )
В школе оно немного иначе проходится: натуральные числа пишутся в столбец (по 3 в каждом ряду) и обводятся в кружочки в цикле каждое 2 и 4 числа, начиная с 5 (2 и 3 в виде исключения тоже). Остальные считаются вычеркнутыми. Получается: 5, 7, 11, 13, 17, 19, 23 (и т. д.).
И на счет 4-го вы ошибаетесь. 3-ий класс = 4 классу. Раньше программа иная была. В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
Другими словами, программа 1-4 класс проходится за 3 года, затем программа 5-11 класс еще за 5 лет. Следующие 2 года идет расширенная программа + предвузовская подготовка.avost
28.09.2016 14:31>Точно не в 3-ем, поэтому точно в 5-ом )
Почему не в 6-ом тогда?
>В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
То есть после девятого можно было поступать в вуз? И с какой тогда целью было тратить на гимназию ещё два года? Бессмыслица какая-то.
Насколько я помню, всё было иначе. Вместо 10-летки ввели 11-летку, а программу не переработали. Поэтому долгое время учились по старой советской программе, просто пропуская в нумерации 4-й класс.LeonidZ
28.09.2016 14:40Потому, что тема простых чисел идет сразу же с темой деления (какие числа делятся только на 1 и самих себя), а умножение и деление мы проходили в 5-ом классе. Это раз.
Второе: моя дочь в прошлом году закончила 5-ый класс, и в середине года мы проходили с ней то же деление, умножение, простые числа, остаток от деления, НОК, НОД и в конце дроби. Т.е. до сих пор простые числа идут в 5 классе (школа обычная).
Далее, по поводу перехода от 10-летки к 11-летке вы абсолютно правы. Но это касается только 1-4 классы за 3 года. Поэтому это не имеет отношения к разнице в программах гимназий и средних школ.
Последний вопрос — зачем в гимназиях 11 классов тогда. Не все программы сжаты до 9 класса. Например, литература идет по стандартной программе, т.к. не каждый ребенок в 11 классе может хоть что-то понять из классики, что говорить о детях на 2 года младше. В 10 и 11 классах обычно очень много выездных лабораторных работ (обычно в ВУЗы) и ВУЗовских преподавателей на расширенной программе в самой школе.avost
28.09.2016 15:44-1>Второе: моя дочь в прошлом году закончила 5-ый класс, и в середине года мы проходили с ней то же деление, умножение, простые числа, остаток от деления, НОК, НОД и в конце дроби. Т.е. до сих пор простые числа идут в 5 классе (школа обычная).
То есть по приведённой ссылке — ложь?
>Не все программы сжаты до 9 класса.
Ну, так я про вашу «сжатую» спрашиваю. Какой смысл оставаться там после 9-го, если можно сразу поступать в вуз? А если планов поступления нет, то тем более.LeonidZ
28.09.2016 15:50Возможно, ваша ссылка на авторскую программу или программу для 12-летки.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
По второму вопросу я ответил, вы просто не так поняли. В сжатой программе не все предметы сжимаются, а примерно половина — две трети. Есть предметы, которые сжать нельзя, и они идут по стандартной программе. А освободившееся время от сжатия части программы используется для ее расширения.avost
28.09.2016 16:53>Возможно, ваша ссылка на авторскую программу или программу для 12-летки.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
Не, может ваша программа — авторская? :)
Куча материалов представляет собой в основном не планы урока про решето, а «проекты» учеников, то есть то, что сверх программы. А программно в основном как раз 6-е классы встречаются. Но один вариант с пятым тоже нашёлся, да.
Впрочем, это не так важно. Видимо, оба варианта есть.
>По второму вопросу я ответил, вы просто не так поняли
Видимо не так. То есть после 9-го в вуз всё-таки нельзя? Тогда 9-й НЕ эквивалентен полному среднему образованию, а эквивалентен советским 8-м классам — неполное среднее. После него не вуз, а в ПТУ/техникум — в совке или колледж, лицей, (не знаю что ещё) — современной терминологии — дополучать образование до среднего специального или среднего профессионального. В таком варианте всё логично и ни чем не отличается по сути от старого. А расширения программы, ну они всегда были. Только называлось это не гимназиями, а спецшколами.LeonidZ
28.09.2016 18:51Я предлагаю вернуться к тому, с чего начали. Тезис «Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе».
«Как и многие 10-летние дети» — согласен, тут не сказано, что все, по всему миру вполне вероятно, что многие.
«В начальной школе» — вот тут у меня серьезные сомнения, т.к. начальная школа — это ДО 5 класса. 5-й класс — это уже средняя школа. Я не нашел ни одной программы изучения решета Эратосфена в 3-х или 4-х классах.avost
28.09.2016 20:31Вы про какую страну? В англии элементари скул до 11 (а было до 14), в штатах до 12. В странах с двухстадийным образованием (праймери, секондари), праймери, как правило, тоже до 12. В нашей начальной, да, не изучают. Именно поэтому человек и сказал — обидненько за наше, якобы, самое лучшее образование.
dro1d
29.09.2016 11:03Программа обучения везде разная, и меняется в зависимости от автора учебника. (очень много знакомых в системе образования, знаю о чем говорю). У кого то тема с простыми числами в 5 классе, у кого то 7. Например, в лицее, где я учился матрицы изучались в 7 классе, хотя обычно их изучают только в ВУЗе.
Chillz
29.09.2016 18:33Кстати, тоже 84 г.р.
1991 (6 лет) — 1 и 2 класс за 1 год
1992 (7 лет) — 3 класс
1993 (8 лет) — 5 класс
1994 (9 лет) — 6 класс
1995 (10 лет) — 7 класс
1996 (11 лет) — 8 класс
1997 (12 лет) — 9 класс
1998 (13 лет) — 10 класс
Остался бы на последний год в гимназии — окончил бы школу в 15.
wormball
28.09.2016 12:37Лично я встречал оное решето в своём учебнике по математике за третий класс (1992 год, москва). И даже вроде бы понял. Только, во-первых, оно там отчего-то называлось решетом Евклида, а во-вторых, на уроках мы его так и не прошли. А ещё там комплексные числа упоминались, но как-то вскользь.
ripatti
28.09.2016 08:32+6Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
molnij
28.09.2016 09:52Спасибо за разъяснение, а то формулировка в статье выглядит по меньшей мере странно
alizar
28.09.2016 10:48>Виноградов доказал не от 1 до N, а от N до бесконечности.
Большое спасибо за пояснение! Поправил в тексте.
Godless
28.09.2016 10:06а кто-нибудь следит за последними достижениями в области факторизации? что-то удачное за последние 10 лет придумали для ускорения факторизации?
vilgeforce
28.09.2016 10:26+1В последние пару лет вышла работа по поиску более хороших полиномов для алгоритма NFS, реализация в cado-nfs включена. Но это улучшение времени не в разы.
Desprit
28.09.2016 13:09Ребят, а можете пару слов сказать вот об этом моменте, пожалуйста?
«Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что граница N в работе Виноградова составляет 10^6 846 168.»
Википедия говорит, что Виноградов говорил о «достаточно большом нечётном числе», а его студент дал нижнюю границу этого числа. Что это означает? Что студент для этого числа посчитал справедливость гипотезы?
mwizard
28.09.2016 13:4528 сентября 2016 в 08:32 пользователь ripatti написал:
Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.Desprit
28.09.2016 14:08То есть, он «добил» все числа до 10^6 846 168?
mwizard
28.09.2016 14:11+1Нет, он доказал, что нижняя граница не 106846168, а 1029, а потом уже до 1029 добил программой. До 106846168 добивать бы пришлось до конца жизни Вселенной, это ж, фактически, 222742478, а доитерироваться в обозримое время даже до 2128 уже проблематично.
Desprit
28.09.2016 15:07Теперь понятно. Собственно, потому и вопрос был, что 10^6846168 — это что-то за гранью понимания вообще.
Спасибо!
mwizard
28.09.2016 13:43+3А где можно ознакомиться с описанием этого алгоритма? Ни одна из ссылок в материале не ведет куда-то, кроме новостных сайтов без деталей.
valis
28.09.2016 14:35Тоже руки чешутся реализовать.
mwizard
28.09.2016 15:14Я нашел его комментарий по этой теме на slashdot, но без подробностей. Люди в публикации ссылаются на вот этот препринт, но я еще не смотрел его на предмет, можно ли из него извлечь достаточно данных для формального описания алгоритма.
Arxitektor
28.09.2016 21:00Теперь понятно. Собственно, потому и вопрос был, что 10^6846168 — это что-то за гранью понимания вообще.
После прочтения а что такое число грема вот там точно за гранью понимания… 10^6846168 это вообще мелочи ))
Robotex
28.09.2016 23:28+1Хороший пример, объясняющий зачем вообще математики доказывают свои теоремы.
daiver19
Во-первых, не верю про гигабайт и килобайт, речь явно об асимптотике. Тем более, если надо хранить простые числа, то сложновато уложиться в такой объем памяти :) Во-вторых, хотелось бы больше деталей об алгоритме. Описание выглядит весьма непонятно, да и временной оценки даже нет.
А еще более интересно узнать реальные результаты. Это, конечно, здорово, что найден такой алгоритм, но что-то мне подсказывает, что он чертовски медленный на практике.
Кстати, блочное решето Эратосфена требует всего sqrt(N) памяти. Этого достаточно, чтоб считать простые числа хоть до 10 в 18й в гигабайтах памяти, плюс можно обрабатывать только нужные окна. Неясно, умеет ли этот новый алгоритм такое. А для совсем больших чисел проще использовать какой-нибудь тест на простоту, всяко быстрее будет.
saboteur_kiev
там гигабайт и мегабайт.
abudnik
В теперешней модели CPU эффективность работы во многом упирается в чтение из памяти. Разница между поместились все данные в кеш процессора или нет может быть радикальна.
В блочном решете нужно не менее O(n^(1/2)) бит памяти. А в приведенном алгоритме O(n^(1/3) * log(n)^(2/3)). Ясно, что вероятность попадания в кеш должна быть больше у нового алгоритма при достаточно больших n. К тому же он имеет O(n) по времени: «y tiempo aun esencialmente linear en N».
daiver19
На счет линейного времени интересно. Что-то мне кажется, что это уже не решето Эратосфена :)
Дополнительный log, кстати, весьма портит картину. Для миллиарда, например, разница всего в 4 раза (допуская одинаковую константу, а я почти уверен, что константа больше). Ну а дальше уже ни о каком кэше речи нет и алгоритм упирается в другие проблемы.
Короче, имхо, очередное занятное теоретическое достижение, которое мы вряд ли увидим в практике.
StarCuriosity
Линейные и даже сублинейные версии решета давно уже известны. Более того, некоторые очень просты.
И да, подобная сложная асимптотика обычно означает какое-нибудь безумное деление на подзадачи и многоуровневую схему. Но почитать статью про алгоритм я бы не отказался.
valis
Ну так называемое блочное решето это лишь оптимизация реализации существующего алгоритма. А здесь, как я понимаю речь идет именно о оптимизации на фундаментальном уровне.
Вообще интересно было бы взглянуть на улучшенный алгоритм и поиграться на практике.