Почему простые числа так важны?

Где важны? В криптографии? Ну потому что вычислительно трудная задача — это именно факторизация большого числа, являющегося произведением двух больших простых чисел. Всё остальное факторизуется легко.

Сами простые числа имеют при этом достаточно случайное распределение.

Матапушта не Райвист, Шамир и Адлеман, а ещё Эйлер, Ферма, Галуа?
А о чём писать? Об алгебраической структуре, обладающей определёнными свойствами по модулю простого числа (DH) — группа, или полупростого числа — кольца и группы "по модулю фи" (RSA). Даже во всякой экзотике с решётками тоже простые числа.

Без простого числа элементарно не получить цикличность группы и конечность поля.

Когда нужны двоичные операции, то для GF(2ⁿ) определяют неприводимый полином — тоже простое число в полиномиальном виде.

Потому что другие числа представимы в виде произведения простых. А вообще вопрос сродни "почему здания строят из кирпечей". Ну технология такая!

Почему диффи-хеллман должен быть по простому модулю?

Имелось в виду "не отвечайте "потому что они используются в RSA", ценность такого ответа равна нулю", что я и написал в вопросе.



Напиши об этом. Я с математикой, стоящей за такого рода криптографией, знаком поверхностно.

Для понимания некоего стандартного набора криптоалгоритмов достаточного совсем небольшого числа базовых понятий из алгебры и теории чисел (всякие экспериментальные направления на экзотических алгебрах пока оставим в стороне). Естественно, сама по себе эта математика известна задолго до того, как её приспособили для криптографии.

Допустим, у нас есть простое число p = 11. У него есть весь ряд (1 ... p-1) мультипликативных инверсий (x · y = 1 mod p):

1	2	3	4	5	6	7	8	9	10
1	6	4	3	9	2	8	7	5	10

а если взять непростое число, то для некоторых членов таких инверсий не будет. Для числа 10 в ряду {1 ... 9} будет только четыре инверсии:

1	2	3	4	5	6	7	8	9
1	-	7	-	-	-	3	-	9

Т.е. хрен вам, а не мультипликативная группа по модулю непростого числа. Зато для всех простых чисел есть полноценные группы с инверсиями и единицами.

Другой пример: в группе по модулю простого числа всегда можно найти генератор, элемент группы, который при возведении в степень даёт все остальные элементы группы (цикличность).

2¹=2 mod 11; 2²=4 mod 11; 2³=8 mod 11; 2⁴=5 mod 11,

а если в виде таблицы:

1	2	3	4	5	6	7	8	9	10
2	4	8	5	10	9	7	3	6	1

Т.е., при возведении некоего генератора в степень по модулю простого числа p получили перестановку всех элементов от 1 до p-1. И это опять же справедливо для каждого простого p.

Более сложные структуры с обратимыми преобразованиями также строятся на основе простых чисел. Отсюда уже выводятся и RSA и DH, и некоторые преобразования в симм. алгоритмах (некоторые S-блоки, MDS-матрицы).

Если так важно, что множество образует группу, не проще ли отказаться от чисел как от одного из её представлений и рассматривать криптографию как некую подобласть абстрактной алгебры? Когда надо будет "заземлить" криптографию в практическую область, после всех доказательств, можно придумать как оптимальней представлять элементы групп (ну или там других алгебраических структур) числами. Более того, произведение таких элементов группы можно определить через "абстрактные стрелки" — оно даже не обязано соответствовать какой-то реальной арифметике, важно лишь чтобы выполнялись замкнутость по операции умножения, ассоциативность, существование обратного и единицы.

Поле картофельное видел? Понимаешь, что оно конечно? Хотя если в деревне не вырос, то да, это непоправимо.

[offtop]
Хотя конечное поле — уникальный объект. Все такие конечные поля изоморфны полю вычетов по модулю простых чисел. И эта специфика полей юзается.
[/offtop]

Это такой петросянистый юмор? Или академический снобизм?
На твоем картофельном поле есть мультипликативно обратный элемент?

Для группы по модулю N мультипликативно обратные элементы будут для всех взаимно простых с N чисел. А где это так важно, чтобы любое число от 1 до N-1 обязательно имело мультипликативно обратный элемент.

А где доказательство существования генератора и как его находят? Опять же, почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?

Есть. Колорадский жук называется.


Борзый мьсе любезно просит unknownа своими славами начать пересказывать учебник по теории групп? Это такой толстый троллинг? Для самых ленивых есть ещё википедия.


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

не проще ли отказаться от чисел как от одного из её представлений и рассматривать криптографию как некую подобласть абстрактной алгебры?

Есть похожие направления, хотя не столь радикально сформулированные.

произведение таких элементов группы можно определить через "абстрактные стрелки"

К концу одной новости упоминается система MQQ.

Когда надо будет "заземлить" криптографию в практическую область, после всех доказательств, можно придумать как оптимальней представлять элементы групп (ну или там других алгебраических структур) числами.

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

---

Там где нужно поле. Хотя в RSA используется кольцо с экспоненциальными инверсиями, но порядок "фи" (p – 1)(q – 1) и здесь вылезает неслучайно. Также как ключ шифрования и расшифрования (ну прямо внезапно, да?) являются обратными множителями (мультипликативными инверсиями) по модулю фи. Т.е. не "простые числа, потому что RSA", а "RSA, DH и ещё куча всего невозможно без простых чисел".

В следствиях из теорем Лагранжа и Эйлера.

Простого алгоритма нет. Есть эвристики и проверки.

Не всегда важно. Важно знать порядок (цикличности) получаемой подгруппы.

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

В DH можно (нужно) использовать генератор не всей группы (примитивный или первообразующий корень), а сильной подгруппы. Так и считать быстрее и стойкость сохраняется. При этом структура подгруппы будет определена свойствами простых чисел. Например, для сильного простого числа p=2q + 1 будет только четыре подгруппы. Тогда можно работать с заведомо сильной подгруппой порядка q. В реальности выбор подгрупп в DH ещё более заоптимизирован. Т.е. можно допустить, чтобы набор убывал, но надо точно заранее показать по порядку подгруппы, насколько он будет убывать. Чтобы не получить слабую подгруппу с малой цикличностью, защититься от атак навязывания слабых подгрупп, утечки информации о логарифме через вычисления по символу Лежандра.

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

А кому он обратен? Твоей маме?


Если дадите понятный и не слишком заучный учебник – буду благодарен. unknown, не то чтобы это была критика, но те, кто могут понять твой пост, вопросов задавать не будут.

Слово "троллинг" каждый определяет для себя, да?

Не поверишь – я там был.

Отправка в поле для наблюдения за картошкой не помогла, да? Что обязан делать солдат, чтобы пользоваться заслуженным уважением офицеров и прапорщиков воинской части?

Напомнило:

^*Cокомнатник по общежитию, мой третий курс.