Слайд из презентации АНБ
В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.
Читать полностью »
В сентябре 2016 прошел очередной ежегодный отбор молодых специалистов, студентов и выпускников инженерных и математических специальностей в школу программистов HeadHunter.
Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.
Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).
Читать полностью »
У числа 60 двенадцать делителей: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
Все знают об удивительных свойствах простых чисел, которые делятся только на самих себя и на единицу. Эти числа исключительно полезны. Относительно большие простые числа (примерно от 10300) используются в криптографии с открытых ключом, в хеш-таблицах, для генерации псевдослучайных чисел и т.д. Кроме огромной пользы для человеческой цивилизации, эти особенные числа поразительно красивы:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199…
Все остальные натуральные числа больше единицы, которые не являются простыми, называются составными. У них несколько делителей. Так вот, среди составных чисел выделяется особая группа чисел, которые можно назвать «суперсоставными» или «антипростыми», потому что у них особенно много делителей. Такие числа всегда являются избыточными.
Читать полностью »
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy
В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.
Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
Читать полностью »
Два математика из Стэнфордского Университета, Каннан Соундараджан [Kannan Soundararajan] и Роберт Лемке Оливер [Robert Lemke Oliver] (на фото выше) обнаружили ранее неизвестное свойство простых чисел. Выяснилось, что шансы на то, что за простым числом, оканчивающимся на 9, будет следовать число, оканчивающееся на 1, на 65% больше, чем шансы, что за ним будет следовать число, снова оканчивающееся на 9. Это предположение было численно проверено компьютерными методами для миллиардов известных простых чисел.
По словам Кена Оно, математика из Университета Эмори в Атланте, это предположение по сути противоречит ожиданиям большинства математиков. Ранее считалось, что простые числа в массе своей ведут себя достаточно случайно. Большинство теоретиков сошлось бы на предположении, что шансы иметь на конце одну из возможных для простых чисел цифр (1, 3, 7, 9) примерно равны для всех таких чисел.
Эндрю Грэнвиль [Andrew Granville] из Монреальского университета, заявил, что «мы занимаемся изучением простых чисел уже очень давно, и никто раньше этого не замечал. Это безумие какое-то. Не могу поверить, что кто-то смог до этого додуматься. Это выглядит очень странно».
Читать полностью »
Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 BC — 300 BC) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.
У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.
Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.
Ко времени появления работы Евклида «Начала» в 300 BC уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
Также он показал, что если число 2n-1 является простым, то число 2n-1 * (2n-1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.
Читать полностью »
Несколько дней назад в комментариях к задаче про возраст Шерил была предложена похожая, но более интересная и сложная задачка, сформулированная таким образом:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Были предложены несколько вариантов решения задачи, в том числе на Scala и C#, предполагающие достаточно грубый перебор множества возможных ответов. Тем не менее, задачу можно решить, если под рукой не оказалось ноутбука, только карандаш и листок бумаги.
Читать полностью »
Автор статьи предлагает заглянуть в то, что представляют собой множества простых чисел, если взглянуть на них геометрическим образом. Это не профессиональная работа, а простое, любительское исследование некоторых любопытных закономерностей. Поэтому, в статье не будет сложной математики, и мы не будем забираться глубоко в ее дебри.
Вероятно, читателю известны многие проблемы, связанные с простыми числами. Их расположение в множестве натуральных чисел неочевидно. Большие простые числа трудно находить, нужно много усилий, чтобы проверить большое число на простоту. На этой трудности основаны многие современные методы криптографии. Мы можем легко перемножить да многозначных простых числа, но зная результат найти исходные множители – очень сложная задача.
Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 раз.
Это и значит, что сложность алгоритма является экспоненциальной, и поэтому какой бы быстрый ни был суперкомпьютер, мы можем подобрать длину числа еще больше, чтобы таких суперкомпьютеров потребовалось миллиард. Правда, стоит уточнить еще раз: находить простые числа для перемножения при этом становится так же все труднее и труднее.
К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, можно, заодно, решить математическую проблему, известную как гипотеза Римана. За ее доказательство математический институт Клея обещает миллион долларов.
Давеча снова увлекся простыми числами. Манит меня их тайна.
Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.
Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!
Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Читать полностью »
Каждое натуральное число обладает очень многими известными и, по-видимому, еще в большем числе неизвестными свойствами. Четные — нечетные, простые — составные, рациональные — иррациональные, целые — дробные, конечные — бесконечные и др. свойства способствуют введению классификации чисел, некоторого порядка в их множестве. Традиционный подход предполагает, что не располагая самим числом (его значением) невозможно определить и его свойства. Но это не совсем так. Ряд полезных свойств для некоторых чисел можно определять не зная их значений, но имея данные об их положении в натуральном ряде чисел (НРЧ). Простыми числами, кроме 2, могут быть только нечетные, а их положение НРЧ определяется нечетной позицией. Сами эти позиции не все равнозначны. Про некоторые большие нечетные N(x1, x2) числа (разумеется в нечетных позициях НРЧ) можно, не пользуясь традиционными (вероятностными) и детерминированным (весьма трудоемким) алгоритмами, однозначно утверждать, они не могут быть простыми.Читать полностью »
