Математики из распределённого проекта по поиску простых чисел GIMPS объявили, что одна из клиентских машин, которая участвует в вычислениях, передала на сервер файл с новым простым числом Мерсенна! Это важное событие для математического сообщества, потому что до сих пор было известно только 44 таких числа, последнее было найдено ровно два года назад.

Числа Мерсенна имеют вид 2ⁿ-1, где n — натуральное число. Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS).

Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 2^32582657-1, имеющему 9.808.358 разрядов. О величине нового числа пока не сообщается. Его проверка идёт уже неделю на двух суперкомпьютерах, процессы завершатся 12 и 16 сентября.

Для нашедшего первое в мире число Мерсенна, которое превысит 10 млн разрядов, предусмотрен денежный приз в размере $100 тыс.

via Scientific American

Последние несколько недель меня не покидают мысли о простых числах. Точнее об оптимизации и параллельных вычислениях при их поиске. В итоге, проснулся я сегодня и начал кодить. В общем, разминка для ума хорошая — много идей, много чего нового узнаю в процессе их реализации. Код падает, отлаживается, ищет все большие простые числа, снова падает и т.д. А в качестве отходов остаются простые числа.
Вот, собственно и вопрос к сообществу — а что бы еще с ними сделать с этими простыми числами, кроме как использовать для поиска больших простых чисел? За любые идеи буду благодарен.
Кстати, если кому нужны простые числа — те, что прога находит лежат тут (это не реклама, если не любите ссылки — не ходите). Пока не в он-лайн режиме, но это еще одна из подзадач.

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

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

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

Приветствую!
Наверное, многие уже слышали о проекте распределенных вычислений по поиску больших простых чисел GIMPS (Great Internet Mersenne Prime Search). На хабре уже проскакивала информация о проекте и его результатах.

Если вы из тех, кто любит разглядывать 12мегабайтные числа в поисках интересностей и просто с целью медитации, не боитесь всё время видеть 100 процентную загрузку CPU (зная, что программа работает с приоритетом «ниже среднего» и практически не влияет на быстродействие машины), а так же хотите внести свой вклад в развитие математики, то прошу под кат.

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

Однако, в зависимости от вида, каждые 7, 11, 13 или 17 лет периодические цикады одновременно массово вылезают на свет и превращаются в шумных летающих тварей, спариваются и вскоре умирают.

Хотя наши странные цикады весело уходят в иной мир, возникает очевидный вопрос: это просто случайность, или числа 7, 11, 13 и 17 какие-то особенные?

В этом посте я расскажу как сделать совершенно бесполезную вещь — вычислять простые числа при помощи шаблонов C++.

Алгоритмы проиллюстрированы кодом на Scheme, поэтому осторожно: скобочки!

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

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

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

В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.

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

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

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

Постановка задачи

Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).

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

Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью симметричного шифрования.

Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

Вступительное слово

По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.

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

До ее написания я сформулировал такие требования к будущей программе:

• Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
• Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
• Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.

Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.

Итак, посмотрим, что получилось.

Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в июне 2009 года.

48-е простое число Мерсенна — 2^57.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате.

Числа Мерсенна имеют вид 2ⁿ-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 2^43.112.609-1, имеющему 12.978.189 десятичных разрядов.

В математике чрезвычайно редко случается, чтобы учёный старше 40 лет опубликовал первую серьёзную научную работу. Ещё реже бывает, чтобы эта работа имела большую научную ценность. Именно такой редчайший случай представляет из себя доцент университета Нью-Гэмпшира Итан Чжан (Yitang Zhang), который до сих не имеет ни должности профессора, ни веб-странички со списком научных работ. Тем не менее, ему удалось совершить серьёзный шаг к решению одной из старейших математических проблем — гипотезе о простых числах-близнецах.

Когда журнал “Annals of Mathematics” получил 17 апреля 2013 года научную работу Чжана, они восприняли её скептически. Заявка на прорывное исследование от неизвестного учёного? Это слишком банально и часто встречается, чтобы оказаться правдой. На удивление редколлегии, несколько научных экспертов подробно изучили работу Чжана — и нашли доказательство гипотезы о расстоянии между парными простыми числами предельно ясным, чётким и бесспорным.

В результате, журнал одобрил работу для публикации в исключительно короткие сроки — уже через три недели после поступления.

Сегодня же пятница, да?

Прочитал совсем недавно довольно известную книгу «Человек, который принял жену за шляпу». Книга действительно стоит быть прочитанной, но я сейчас не об этом.

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

Для начала небольшой спойлер

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

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

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

В мае на Хабре была опубликована статья, которая повествует о работе Yitang Zhang в области теории простых чисел, вызвавшей большой резонанс в научном сообществе. В этой заметке даётся краткая сводка результатов, которых удалось достичь научному сообществу спустя девять месяцев с момента публикации этой работы.