Алгоритм перестановки целых функций - PullRequest
Новая
       10

Алгоритм перестановки целых функций

0 голосов
/ 30 октября 2010

Я хочу написать некоторые функции следующим образом

y = f (x) и другая функция,
х = г (у), который действует как обратимый, где
y = f (g (y)) и где x и y - переставленные целые числа.

Для очень простого примера в диапазоне целых чисел от 0 до 10 это будет выглядеть так: 

0->1  
1->2  
2->3  
...  
9->10  
10->0

но это самый простой метод - сложить 1 и обратить вспять, вычтя 1.

Я хочу иметь более изощренный алгоритм, который может делать следующее: 

234927773->4299  
34->33928830  
850033->23234243423

но обратное можно получить преобразованием

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

Ответы [ 3 ]

1 голос
/ 30 октября 2010

Вы могли бы просто XOR. 

y = x XOR p
x = y XOR p

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

1 голос
/ 01 ноября 2010

Если домен вашей перестановки имеет степень 2, вы можете использовать любой блочный шифр: «f» - это шифрование с определенным ключом, а «g» - дешифрование с тем же ключом.Если ваш домен не имеет степени 2, вы все еще можете использовать блочный шифр: см. эту статью .

0 голосов
/ 30 октября 2010

Вы можете использовать методы полиномиальной интерполяции для интерполяции функции одним способом, а затем выполнить обратную интерполяцию, чтобы найти обратную функцию.

Вот пример кода в MATLAB: 

function [a] = Coef(x, y)
    n = length(x);

    a = y;
    for j = 2:n
        for i = n:-1:j
            a(i) = (a(i) - a(i-1)) / (x(i) - x(i-j+1));
        end
    end
end

function [val] = Eval(x, a, t)
    n = length(x);

    val = a(n);
    for i = n-1:-1:1
       val = a(i) + val*(t-x(i)); 
    end
end

Он строит таблицу разделенных разностей и оценивает функцию на основе интерполяции Ньютонов.

Тогда, если ваши наборы точекравны x и y (как векторы одинаковой длины, где x (i) соответствует y (i), ваша функция прямой интерполяции при значении n будет Eval(x, Coef(x, y), n), а функция обратной интерполяции будет Eval(y, Coef(y, x), n).

В зависимости от вашего языка, возможно, есть гораздо более чистые способы сделать это, но это не совсем понятно из математики.

Вот выдержка из учебника, которая используется в моих численных методахкласс: Google Book Link

...