[математикам]что такое mod?

а вроде всегда это был остаток от деления. число, не превосходящее делитель.

если по простому, то это как будто "зацикленное" отнимание. т.е. какое останется число k, если от числа n отнять число m максимум полных раз.
например. 11 mod 3 = 2. число 11 это 3+3+3+2. результат - 2. 61 mod 26 = 9. 61 это 26+26+9.

//читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

про (mod p-1) уже сказали, но

> d = e^-1 (mod p-1) = 42239^-1 (mod(52631-1) = 32229

либо очепятка, либо ошибка:

a^{-1}=b(mod c) если a*b=1(mod c), но у тут

42239*32229=45781(mod 52630)

кури теорию чисел

Ужас. Закрывай методичку, открывай теорию чисел. А то что будет, когда дискретные логарифмы (ЕМНИП, ГОСТовское шифрование на них основано, но тут могу ошибаться, лет 10 криптографию не трогал) встретишь и т.д.

ОМГ, так это ты подпускаешь людей без знания математики к криптографии?

> //читаю лекции по криптографии у людей с большими провалами в математике, даже поля Галуа и теорему Ейлера можно объяснить на пальцах, ящитаю

Объясните на пальцах БПФ. Не что он делает, а КАК.

Ну мля, я хочу понять, как всё-таки эти формулы с интегралами в циклы расписать чтобы ему на вход массив с PCM, на выходе массив с частотами.

Здесь либо порядок операций нужно смотреть, либо ограничение представления машинного числа в памяти компа. Положительное integer принимает значения от 0 до 32767. Ну, типа тогда 0-1=32767.

Ну что такое остаток я понимаю, но как его найти в данном примере? Ведь e^{-1} явно меньше чем (p-1)?

p.s. эта формула из "трехподходного протокола Шамира"

>Как это считается?

Самое простое объяснение: в методичке опечатка, пропущена какая-то буква перед "-1".

Второе объяснение - вопрос в том, что такое e^-1 в смысле (mod n), и как его вычислить.

Это таки точно опечатка. У меня получается 34229, что слишком похоже на 32229, чтобы быть случайным.

Т.е. получается: d = e^{-1} (mod p-1) = 42239^{-1} (mod(52631-1) = 34229

Еще раз, для малограмотных, объясните как взять остаток от деления 42239^{-1} = 2.36748029073e-05 на 52630?

>как взять остаток от деления 42239^{-1}

На самом деле mod(n), означает не остаток от деления(это только метод вычисления) а выполнение операций в соотв. кольце (или какой другой структуре -- я основательно позабыл) - в котором не-целых чисел вообще нет, т.ч. e-05 там получить никак нельзя. Т.о. из определения ^-1: A^-1 (mod N) = B, такое, что A * B (mod n) = 1, следует немножко другое число. Как его вычислить и правда не знаю (:for i in range() помог:). Опыт показывает, что это 34229, т.к. *42239 mod (52630) == 1.

Спасибо, тогда тоже пока напишу скрипт, пусть ищет.

Это та самая лаба по RSA? :-D

>На самом деле mod(n), означает не остаток от деления(это только метод вычисления) а выполнение операций в соотв. кольце

Конечное поле же

ЗЫ: топикстартеру читать про кольца, поля, поля Галуа, модульную арифметику

RSA уже сделал, теперь вот протокол Шамира :-)

> выполнение операций в соотв. кольце (или какой другой структуре -- я основательно позабыл)

кольце

>>даже поля Галуа и теорему Эйлера можно объяснить на пальцах, ящитаю

+1000 Только 99% вкуривших эту простоту математиков - трусливые кретины - умышленно скрывают эту простоту от якобы непосвященных, запутывают ненаглядными корявыми формулировками, монополизируя науку, боясь разоблачения. Эхх.. если бы все преподы объясняли бы как Арнольд.

это операции по модулю у Кнута есть и в книгах по алгоритмам описываются

в данном случае 42239^{-1} != 2.36748029073e-05 !!!

x=42239^(-1) mod N означает, что x- такое число которое в кольце вычетов по модулю N дает единицу.

т.е. (42239*(42239^-1))mod N = 1

при этом x- целое число не превышающее N. алгоритм поиска вспоминать лениво, но было еще что-то кроме перебора кажется.

>d = e^-1 (mod p-1)

Это означает: d = e^1 + k*(p-1), k из рассматриваемого конечного поля

s/e^1/e^-1/

> Только 99% вкуривших эту простоту математиков - трусливые кретины - умышленно скрывают эту простоту от якобы непосвященных, запутывают ненаглядными корявыми формулировками, монополизируя науку, боясь разоблачения.

в правительстве сидят инопланетяне, ага. Во-первых, сложность (реальная) кроется в объёме информации, которую нужно усвоить для того чтобы понимать это. Во-вторых, объяснять тоже умеют не все.

Может имеется в виду обратный элемент в поле или кольце вычетов? То есть 42239^{-1} = 52630 - 42239. Ибо в этих кольцах никаких нецелых чисел нини. Короче форматирование и саму методичку в студию

> Может имеется в виду обратный элемент в поле или кольце вычетов? То есть 42239^{-1} = 52630 - 42239.

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