Рубрика «простые числа» - 6

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

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

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

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

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

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал 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).

На днях дошли руки, что бы рабочее месиво «лишь бы посчитать, да побыстрее» причесать и извлечь оттуда модуль генерации простых чисел. Зачем это надо? Кому-то пригодиться как ещё-один-модуль-на-питоне. Кто-то может увидеть ещё один пример того, как писать не надо. А я, надеюсь, получу порцию тонизирующей критики и прочих советов.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js