В мае на Хабре была опубликована статья, которая повествует о работе Yitang Zhang в области теории простых чисел, вызвавшей большой резонанс в научном сообществе. В этой заметке даётся краткая сводка результатов, которых удалось достичь научному сообществу спустя девять месяцев с момента публикации этой работы.
Метка «простые числа»
Коллективный разум в теории чисел
2014-02-02 в 13:35, admin, рубрики: математика, простые числа, теория чисел, метки: математика, простые числа, теория чиселО простых числах, криптографии и повреждениях мозга
2013-08-30 в 12:29, admin, рубрики: аутизм, криптография, математика, простые числа, метки: аутизм, криптография, математика, простые числаСегодня же пятница, да?
Прочитал совсем недавно довольно известную книгу «Человек, который принял жену за шляпу». Книга действительно стоит быть прочитанной, но я сейчас не об этом.
В одном из сюжетов автор — практикующий врач, работающий с людьми с разной степенью повреждения мозга, сталкивается с близнецами-аутистами, играющими друг с другом в игру. Сначала один из них называет шестизначное число, через какое-то время другой явно этому чилу радуется, словно что-то в нем разглядев, и в свою очередь, называет другое шестизначное число. Процесс повторяется много раз.
Читать полностью »
О простых числах. Поиск на Java
2013-08-17 в 12:50, admin, рубрики: java, алгоритм поиска, Алгоритмы, Программирование, простые числа, метки: java, алгоритм поиска, Программирование, простые числа 
Всем хорошего дня!
На Хабре уже не раз упоминали об этих чудо-числах.
Конечно перечислять все я не буду, достаточно просто заглянуть сюда.Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Читать полностью »
Оптимизированный алгоритм поиска больших простых чисел для генерации асимметричных ключей
2013-07-09 в 5:01, admin, рубрики: rsa, информационная безопасность, криптография, математика, простые числа, метки: rsa, криптография, простые числа Идея этого алгоритма пришла мне в голову ещё в 2006 на лекции по криптографии, как раз посвящённой алгоритму RSA. На ней говорилось, что большое число x из диапазона 22000÷24000 считается простым если удовлетворяет неким критерии простоты и если остальные числа в его окрестностях (x-2000;x) являются составными. Тогда меня удивило, зачем проверять все ближайшие числа на простоту, если можно специально выбирать числа, рядом с которыми в заданном диапазоне все соседи являются составными по-умолчанию? Алгоритм был придуман, описан и опубликован в университетском сборнике, но т.к. их никто не читает, то опубликую его здесь. Авось, кому-то пригодится;)
Читать полностью »
Неизвестный математик совершил прорыв в теории простых чисел-близнецов
2013-05-20 в 6:09, admin, рубрики: математика, простые числа, метки: простые числа 
В математике чрезвычайно редко случается, чтобы учёный старше 40 лет опубликовал первую серьёзную научную работу. Ещё реже бывает, чтобы эта работа имела большую научную ценность. Именно такой редчайший случай представляет из себя доцент университета Нью-Гэмпшира Итан Чжан (Yitang Zhang), который до сих пор даже не имеет ни звания профессора, ни веб-странички со списком научных работ. Тем не менее, ему удалось совершить серьёзный шаг к решению одной из старейших математических проблем — теореме о простых числах-близнецах.
Когда журнал “Annals of Mathematics” получил 17 апреля 2013 года научную работу Чжана, они восприняли её скептически. Заявка на прорывное исследование от неизвестного учёного? Это слишком банально и часто встречается, чтобы оказаться правдой. На удивление редколлегии, несколько научных экспертов подробно изучили работу Чжана — и нашли доказательство гипотезы о расстоянии между парными простыми числами предельно ясным, чётким и бесспорным.
В результате, журнал одобрил работу для публикации в исключительно короткие сроки — уже через три недели после поступления.
Читать полностью »
Найдено 48-е простое число Мерсенна
2013-02-05 в 19:39, admin, рубрики: высокая производительность, математика, простые числа, метки: простые числаМатематики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в 2009 году.
48-е простое число Мерсенна — 257.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате (22,45 мегабайта).
Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 243.112.609-1, имеющему 12.978.189 десятичных разрядов.
Читать полностью »
Простая программа на ассемблере x86: Решето Эратосфена
2013-01-10 в 23:15, admin, рубрики: x86, простые числа, метки: x86, ассемблер, простые числаВступительное слово
По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.
И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства x86, с разбора которой можно начать свой путь в покорение низин уровней абстракции.
До ее написания я сформулировал такие требования к будущей программе:
- Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
- Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
- Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.
Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.
Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.
Итак, посмотрим, что получилось.Читать полностью »
Алгоритм Диффи — Хеллмана
2012-09-17 в 9:39, admin, рубрики: алгоритм, Алгоритмы, дискретный логарифм, криптография, математика, простые числа, шифрование, метки: алгоритм, дискретный логарифм, криптография, математика, простые числа, шифрованиеОдна из фундаментальных проблем криптографии – безопасное общение по прослушиваемому каналу. Сообщения нужно зашифровывать и расшифровывать, но для этого обеим сторонам нужно иметь общий ключ. Если этот ключ передавать по тому же каналу, то прослушивающая сторона тоже получит его, и смысл шифрования исчезнет.
Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью Читать полностью »
Быстрое индексное умножение по модулю
2012-08-08 в 11:52, admin, рубрики: Алгоритмы, дискретный логарифм, простые числа, Электроника для начинающих, метки: дискретный логарифм, простые числаВведение
Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.
Постановка задачи
Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).
Читать полностью »
Модуль генерации простых чисел
2012-05-01 в 12:13, admin, рубрики: project euler, python, математика, простые числа, метки: project euler, python, математика, простые числаКто-то любит горы Кавказа, кто-то горы кокоса...
… а мне нравится решать задачи Project Euler. Конечно, я не могу похвастаться 350+ решёнными задачами, но четвёртый уровень (100..125) набрал честно. И в процессе этого набора, как подобает разработчику обыкновенному, начал выносить повторяющиеся фрагменты в отдельный модуль.
Надо сказать, что, по моим ощущениям, не менее половины представленных задач так или иначе связано с простыми числами. Например, найти наименьшие 5 простых чисел, таких, что любая пара из них, записанная в любом порядке как одно число (34, 56 -> 3456) будет так же простым числом (60). Или найти 1<=n<=1000000, такое что n/phi(n) максимально (69).
На днях дошли руки, что бы рабочее месиво «лишь бы посчитать, да побыстрее» причесать и извлечь оттуда модуль генерации простых чисел. Зачем это надо? Кому-то пригодиться как ещё-один-модуль-на-питоне. Кто-то может увидеть ещё один пример того, как писать не надо. А я, надеюсь, получу порцию тонизирующей критики и прочих советов.