генерирование перестановок с помошью полиномов??

[eugrita]

Известен прием используемый в некоторых алгоритмах шифрования (алгоритмы замены) где для каждого i-элемента множества мощности n генерируется перестановка по формуле $j=mod(k_1*i+k_2, n)$
(здесь mod(m,n) означает остаток деления m на n
Когда используется линейное преобразование нет проблем с обратимостью (декодированием). Но стоит только повысить степень полинома выше 1 - начинаются проблемы. Образы некоторых элементов "склеиваются", нарушается иньективность отображения.
Мой вопрос в следующем - какие можно сформулировать требования к полиномам $P_n(x)$ чтобы отображение
$j=mod(P_n(i), n) $ было перестановкой ?
(инъективным, биективным ). Мне кажется здесь есть некоторая аналогия с циклическими группами
Прошу меня заранее извинить за будущую пассивность в обсуждении темы в будущем, в связи с моим отъездом с 01.05 по 10.05 в место где нет интернета

[Sonic86]

Мдя, таких многочленов либо мало, либо нет. К примеру квадратичные функции, исключая несколько тривиальных случаев, всегда дают небиективное отображение.
Если $\text{НОК}(k,n)=1$, то $P(x)=(Ax^k+B) \mod n$ дает перестановку.

С другой стороны, для простых модулей все нужные подстановки Вы можете построить с помощью полиномов Лагранжа. Т.е. если $n$ - простое, то $x^{n-1} \equiv 1 \pmod n$ для всех $x: x \not \equiv 0 \pmod n$, иначе $x^{n-1} \equiv 0 \pmod n$. Затем строим из таких многочленов нужные линейные комбинации.

-- Чт апр 28, 2011 14:01:25 --

(формулы)

умножение пишется как $\cdot$, еще можете остаток написать как $\mod$

[eugrita]

Возможно. Недостаточно владею областью. Правильно ли понимаю, что конечное множество (массив) алфавит является конечным полем (определ оп умн эл и сложение). Но если допускаем в качестве формул полиномы с веществ коэфф это не будут полиномы над полем. И всякие разговоры о цикломатических классах можно в нашем случае отбросить. С конечным полем нас здесь связывает только операция mod
Кроме того непонятно, что это за полиномы Лагранжа - во всяком случае не интерполяционные полиномы Лагранжа?
Спасибо за приведенный пример с НОД(n,k)=1 пусть это перестановка, но можно ли обратную перестановку в этом случае построить по формуле, не запоминая обе в массивы?

[Sonic86]

Ну да, конечное поле. Никаких вещественных коэффициентов - просто вычеты, изображаются целыми числами.

eugrita писал(а):

Кроме того непонятно, что это за полиномы Лагранжа - во всяком случае не интерполяционные полиномы Лагранжа?

Не, это именно они

-- Чт апр 28, 2011 14:57:10 --

eugrita писал(а):

Спасибо за приведенный пример с НОД(n,k)=1 пусть это перестановка, но можно ли обратную перестановку в этом случае построить по формуле, не запоминая обе в массивы?

Ну да, конечно. Если $P(x)=x^k$, $\text{НОК}(k,n)=1$, то найдется $m: km \equiv 1 \pmod n$, и тогда для $Q(x)=x^m$ будет $Q(P(x)) \equiv x \pmod n$. Для случая $P(x)=Ax^k+B$, думаю, сами сможете построить обратную функцию.

[eugrita]

Насколько понимаю в криптографии (в отличие от математики) хотят не обобщать закономерности, а стремятся к разнообразию шифров. В этом смысле полином с вещественными коэфф оправдан, т.к $[mod(P_m(i),n)]$ определен (округляем остаток от деления до целого отбрасыванием дробн части).
Но опять вопрос а есть ли обратное преобразование по какой-то формуле?

[Kallikanzarid]

Например, $P(x) = k_0 + k_3 x^3 + k_5 x^5 + \ldots$, все $k_i$ неотрицательные, сойдет? Функция $P(x)$ строго монотонная: $P'(x) = 3 k_3 x^2 + 5 k_5 x^4 _ \ldots = 0$ тогда и только тогда, когда $x = 0$, в этой точке будет перегиб.

[Sonic86]

eugrita писал(а):

Насколько понимаю в криптографии (в отличие от математики) хотят не обобщать закономерности, а стремятся к разнообразию шифров. В этом смысле полином с вещественными коэфф оправдан, т.к $[mod(P_m(i),n)]$ определен (округляем остаток от деления до целого отбрасыванием дробн части).

Вы хотите даже такие функции (это не полиномы, кстати). Тогда сложнее. Я вот лично для заданного $n$ и $P_3(x)$ пока затрудняюсь ответить в общем, будет ли отображение биективным или нет. А эти анализировать еще сложнее будет. Насчет обратного преобразования для них тоже затрудняюсь что-либо сказать.

[Kallikanzarid]

eugrita в сообщении #439385 писал(а):

Насколько понимаю в криптографии (в отличие от математики) хотят не обобщать закономерности, а стремятся к разнообразию шифров.

Security through obscurity - не труъ.

[Joker_vD]

Насколько я понял, вы хотите знать, можно ли в конечном поле задать перестановку многочленом от одной переменной?

[eugrita]

Ладно. Спасибо за сочуствие. Временно прекращаю обсуждение, т.к на работе - на паре.
Да именно это:
можно ли в конечном поле задать перестановку многочленом от одной переменной? Но не только для многочлен над полем а и для многочлена с вещественными коэфф

[Portnov]

Упорно лезут в голову группы Галуа для многочленов, которые, как известно, изоморфны некоторым группам перестановок конечных множеств. Кажется, это как-то может помочь, но плохо представляю, как именно :/

[Хорхе]

Portnov в сообщении #439619 писал(а):

Упорно лезут в голову группы Галуа для многочленов, которые, как известно, изоморфны некоторым группам перестановок конечных множеств.

Открою небольшой секрет -- Галуа тут кагбе и ни при чем: все конечные группы какой-то такой хренотени изоморфны.

[Portnov]

Просто тут многочлены причём, вот и лезут в голову именно группы Галуа.

[Kallikanzarid]

Хорхе в сообщении #439638 писал(а):

Открою небольшой секрет -- Галуа тут кагбе и ни при чем: все конечные группы какой-то такой хренотени изоморфны.

Вообще все группы.

[VAL]

Р. Лидл, Г. Нидеррайтер. Конечные поля. Т.2, гвава 7 (первая глава во втором томе).