Для начала небольшой спойлер
Да я знаю, что если написать фамилию с заглавной буквы, казуса не получится. Дальше перевод.
Математика – одна из немногих областей знаний, которая может быть объективно названа истинной, потому что ее теоремы основаны на чистой логике. Но в то же время эти теоремы часто оказываются очень странными и противоречащими интуиции.
Некоторые люди считают математику скучной. Следующие примеры показывают, что она какая угодно, но не такая
Читать полностью »
Сегодня же пятница, да?
Прочитал совсем недавно довольно известную книгу «Человек, который принял жену за шляпу». Книга действительно стоит быть прочитанной, но я сейчас не об этом.
В одном из сюжетов автор — практикующий врач, работающий с людьми с разной степенью повреждения мозга, сталкивается с близнецами-аутистами, играющими друг с другом в игру. Сначала один из них называет шестизначное число, через какое-то время другой явно этому чилу радуется, словно что-то в нем разглядев, и в свою очередь, называет другое шестизначное число. Процесс повторяется много раз.
Читать полностью »
На Хабре уже не раз упоминали об этих чудо-числах.
Конечно перечислять все я не буду, достаточно просто заглянуть сюда.Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Читать полностью »
Идея этого алгоритма пришла мне в голову ещё в 2006 на лекции по криптографии, как раз посвящённой алгоритму RSA. На ней говорилось, что большое число x из диапазона 22000÷24000 считается простым если удовлетворяет неким критерии простоты и если остальные числа в его окрестностях (x-2000;x) являются составными. Тогда меня удивило, зачем проверять все ближайшие числа на простоту, если можно специально выбирать числа, рядом с которыми в заданном диапазоне все соседи являются составными по-умолчанию? Алгоритм был придуман, описан и опубликован в университетском сборнике, но т.к. их никто не читает, то опубликую его здесь. Авось, кому-то пригодится;)
Читать полностью »
В математике чрезвычайно редко случается, чтобы учёный старше 40 лет опубликовал первую серьёзную научную работу. Ещё реже бывает, чтобы эта работа имела большую научную ценность. Именно такой редчайший случай представляет из себя доцент университета Нью-Гэмпшира Итан Чжан (Yitang Zhang), который до сих пор даже не имеет ни звания профессора, ни веб-странички со списком научных работ. Тем не менее, ему удалось совершить серьёзный шаг к решению одной из старейших математических проблем — теореме о простых числах-близнецах.
Когда журнал “Annals of Mathematics” получил 17 апреля 2013 года научную работу Чжана, они восприняли её скептически. Заявка на прорывное исследование от неизвестного учёного? Это слишком банально и часто встречается, чтобы оказаться правдой. На удивление редколлегии, несколько научных экспертов подробно изучили работу Чжана — и нашли доказательство гипотезы о расстоянии между парными простыми числами предельно ясным, чётким и бесспорным.
В результате, журнал одобрил работу для публикации в исключительно короткие сроки — уже через три недели после поступления.
Читать полностью »
Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в 2009 году.
48-е простое число Мерсенна — 257.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате (22,45 мегабайта).
Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 243.112.609-1, имеющему 12.978.189 десятичных разрядов.
Читать полностью »
По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.
И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства x86, с разбора которой можно начать свой путь в покорение низин уровней абстракции.
До ее написания я сформулировал такие требования к будущей программе:
Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.
Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.
Итак, посмотрим, что получилось.Читать полностью »
Одна из фундаментальных проблем криптографии – безопасное общение по прослушиваемому каналу. Сообщения нужно зашифровывать и расшифровывать, но для этого обеим сторонам нужно иметь общий ключ. Если этот ключ передавать по тому же каналу, то прослушивающая сторона тоже получит его, и смысл шифрования исчезнет.
Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью Читать полностью »
Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.
Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).
Читать полностью »
Кто-то любит горы Кавказа, кто-то горы кокоса...
… а мне нравится решать задачи Project Euler. Конечно, я не могу похвастаться 350+ решёнными задачами, но четвёртый уровень (100..125) набрал честно. И в процессе этого набора, как подобает разработчику обыкновенному, начал выносить повторяющиеся фрагменты в отдельный модуль.
Надо сказать, что, по моим ощущениям, не менее половины представленных задач так или иначе связано с простыми числами. Например, найти наименьшие 5 простых чисел, таких, что любая пара из них, записанная в любом порядке как одно число (34, 56 -> 3456) будет так же простым числом (60). Или найти 1<=n<=1000000, такое что n/phi(n) максимально (69).
На днях дошли руки, что бы рабочее месиво «лишь бы посчитать, да побыстрее» причесать и извлечь оттуда модуль генерации простых чисел. Зачем это надо? Кому-то пригодиться как ещё-один-модуль-на-питоне. Кто-то может увидеть ещё один пример того, как писать не надо. А я, надеюсь, получу порцию тонизирующей критики и прочих советов.
