| |
|
  |
 Обратное соответствие (x*y) mod z, Как нибудь аналитечески можно ли? |
|
|
|
|
 Jan 19 2011, 21:34
|
Профессионал
Группа: Свой
Сообщений: 1 284
Регистрация: 9-04-06
Пользователь №: 15 968
|
Добрый день, Уважаемые. Туплю че-то, подскажите пожалуйста.
Такая задача: найти обратное соответствие функции a = (x*y) mod z.
Известно: a,y,z, надо найти x. Кроме того, z<<y и точно известно, что соответствие между a и х однозначное.
Можно ли как то аналитически вычислить x, зная a? Можно конечно через таблицу, вычислить прямое соответствие а потом обратное искать, но память тратить на таблицу неохота.
Спасибо.
|
|
|
|
|
|
|
|
Jan 19 2011, 23:08
|
Гуру
Группа: Модератор FTP
Сообщений: 4 479
Регистрация: 20-02-08
Из: Москва
Пользователь №: 35 237
|
Цитата(alexPec @ Jan 20 2011, 00:34)  Такая задача: найти обратное соответствие функции a = (x*y) mod z.
Известно: a,y,z, надо найти x Ответ: x = (n*z + a)/y, где n - любое натуральное число. Проверка: 1) домножая обе части на y, получим: x*y = n*z + a 2) берем модуль от обеих частей: (x*y) mod z = (n*z+a) mod z = a что совпадает c условием.
|
|
|
|
|
|
|
|
Jan 20 2011, 10:15
|
Профессионал
Группа: Свой
Сообщений: 1 284
Регистрация: 9-04-06
Пользователь №: 15 968
|
Осмыслил, но не понял как это может помочь в решении обратной задачи.
Чтоб было понятно о чем речь, это функция рандомизации последовательности от 0 до Z, упрощенный пример:
a=(x*13) mod 5
Соответствие такое, как видно однозначное (да, забыл упомянуть, 0<=x<z, х целое):
Х - а
0 - 0
1 - 3
2 - 1
3 - 4
4 - 2
Нужно по последовательности a восстановить последовательность Х
Че то даже на таком простом примере не соображу аналитическое решение обратной задачи.
Вопрос ставится уже так: имеет ли задача обратное решение (кроме табличного)?
Помню обрывками из криптографии, что однозначность только имеет прямая задача, а обратная однозначно не решается. Или я что-то путаю?
Если мысли мои верны, то подскажите, возможно ли как-то решить обратную задачу без таблицы, ну или таблицу не размером 2 x Z, а поменьше делать?
И еще раз спасибо.
|
|
|
|
|
|
|
|
Jan 20 2011, 11:40
|
Участник
Группа: Участник
Сообщений: 60
Регистрация: 21-11-08
Пользователь №: 41 832
|
Вычисляй по Цитата(Xenia @ Jan 20 2011, 02:08) Ответ: x = (n*z + a)/y, где n - любое целое число. Для твоего примера: a=(x*13) mod 5 Код int n;
for( n=0; n< 1000 /*Должен же быть какой-то предел */; n++)
{
int temp;
temp = n*5 + a;
if( (temp % y) == 0 )
{
// Ответ
printf("%d", temp / y);
break;
}
}
Сообщение отредактировал ucMike - Jan 20 2011, 11:42
Эскизы прикрепленных изображений
|
|
|
|
|
|
|
|
Jan 20 2011, 12:47
|
Профессионал
Группа: Свой
Сообщений: 1 284
Регистрация: 9-04-06
Пользователь №: 15 968
|
Цитата(Oldring @ Jan 20 2011, 15:08) Алгоритм Евклида поможет. Спасибо. Цитата Забыли сказать? Да вы просто издеваетесь! Может быть у вас еще y тоже целое? Ну я же говорю, туплю  . А про у - да, тоже целое!  2 ucMike : Перебором? А что, тоже вариант! Спасибо.
|
|
|
|
|
|
|
|
Jan 20 2011, 15:04
|
Знающий
Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730
|
Цитата Oldring:
"Обратный от y" - это целочисленное решение уравнения 1 = (x * y) mod z Или y^-1 = y^(m-2) mod m (m - простое) 13^(5-2) mod 5 = 2 Следствие из малой теоремы ферма...
|
|
|
|
|
|
|
|
Feb 2 2011, 10:23
|
Местный
Группа: Свой
Сообщений: 330
Регистрация: 10-06-05
Из: Россия, Москва
Пользователь №: 5 894
|
А решение такого уравнения никто не подскажет?  x = ( y ^ 3 ) mod ( 2 ^ 160 ) Где: x - известно, у - необходимо найти
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
