Добрый день, Уважаемые. Туплю че-то, подскажите пожалуйста.
Такая задача: найти обратное соответствие функции a = (x*y) mod z.
Известно: a,y,z, надо найти x. Кроме того, z<<y и точно известно, что соответствие между a и х однозначное.
Можно ли как то аналитически вычислить x, зная a? Можно конечно через таблицу, вычислить прямое соответствие а потом обратное искать, но память тратить на таблицу неохота.
Спасибо.
Полная версия этой страницы: Обратное соответствие (x*y) mod z
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
QUOTE (alexPec @ Jan 19 2011, 23:34) 
и точно известно, что соответствие между a и х однозначное
Вот этот момент подробнее осветите. Разве решением не будет бесконечное множество x?
Цитата(alexPec @ Jan 20 2011, 00:34)
Такая задача: найти обратное соответствие функции a = (x*y) mod z.
Известно: a,y,z, надо найти x
Известно: 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 условием.
Цитата(Xenia @ Jan 20 2011, 02:08)
Ответ: 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 условием.
Проверка:
1) домножая обе части на y, получим:
x*y = n*z + a
2) берем модуль от обеих частей:
(x*y) mod z = (n*z+a) mod z = a
что совпадает c условием.
Спасибо Xenia, осмылю - отпишусь.
Осмыслил, но не понял как это может помочь в решении обратной задачи.
Чтоб было понятно о чем речь, это функция рандомизации последовательности от 0 до Z, упрощенный пример:
a=(x*13) mod 5
Соответствие такое, как видно однозначное (да, забыл упомянуть, 0<=x<z, х целое):
Х - а
0 - 0
1 - 3
2 - 1
3 - 4
4 - 2
Нужно по последовательности a восстановить последовательность Х
Че то даже на таком простом примере не соображу аналитическое решение обратной задачи.
Вопрос ставится уже так: имеет ли задача обратное решение (кроме табличного)?
Помню обрывками из криптографии, что однозначность только имеет прямая задача, а обратная однозначно не решается. Или я что-то путаю?
Если мысли мои верны, то подскажите, возможно ли как-то решить обратную задачу без таблицы, ну или таблицу не размером 2 x Z, а поменьше делать?
И еще раз спасибо.
Чтоб было понятно о чем речь, это функция рандомизации последовательности от 0 до Z, упрощенный пример:
a=(x*13) mod 5
Соответствие такое, как видно однозначное (да, забыл упомянуть, 0<=x<z, х целое):
Х - а
0 - 0
1 - 3
2 - 1
3 - 4
4 - 2
Нужно по последовательности a восстановить последовательность Х
Че то даже на таком простом примере не соображу аналитическое решение обратной задачи.
Вопрос ставится уже так: имеет ли задача обратное решение (кроме табличного)?
Помню обрывками из криптографии, что однозначность только имеет прямая задача, а обратная однозначно не решается. Или я что-то путаю?
Если мысли мои верны, то подскажите, возможно ли как-то решить обратную задачу без таблицы, ну или таблицу не размером 2 x Z, а поменьше делать?
И еще раз спасибо.
Вычисляй по
где n - любое целое число.
Для твоего примера: a=(x*13) mod 5
Цитата(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;
}
}
for( n=0; n< 1000 /*Должен же быть какой-то предел */; n++)
{
int temp;
temp = n*5 + a;
if( (temp % y) == 0 )
{
// Ответ
printf("%d", temp / y);
break;
}
}
Цитата(alexPec @ Jan 20 2011, 00:34)
Такая задача: найти обратное соответствие функции a = (x*y) mod z.
Известно: a,y,z, надо найти x.
Известно: a,y,z, надо найти x.
Алгоритм Евклида поможет.
Цитата(alexPec @ Jan 20 2011, 13:15)
Соответствие такое, как видно однозначное (да, забыл упомянуть, 0<=x<z, х целое)
Забыли сказать? Да вы просто издеваетесь! Может быть у вас еще y тоже целое?
Цитата(Oldring @ Jan 20 2011, 15:08)
Алгоритм Евклида поможет.
Спасибо.
Цитата
Забыли сказать? Да вы просто издеваетесь! Может быть у вас еще y тоже целое?
Ну я же говорю, туплю
. А про у - да, тоже целое! 
2 ucMike : Перебором? А что, тоже вариант! Спасибо.
Цитата(alexPec @ Jan 20 2011, 15:47)
Спасибо.
А если y и z фиксированы и известны заранее, то умножьте a та обратный от y, всё по модулю z.
"Обратный от y" - это целочисленное решение уравнения 1 = (x * y) mod z
Цитата
Oldring:
"Обратный от y" - это целочисленное решение уравнения 1 = (x * y) mod z
"Обратный от y" - это целочисленное решение уравнения 1 = (x * y) mod z
Или y^-1 = y^(m-2) mod m (m - простое) 13^(5-2) mod 5 = 2
Следствие из малой теоремы ферма...
Oldring, Thermit - ГОСПОДА, ВЫ МОНСТРЫ!!
В жизни бы не вспомнил эту теорему Ферма, и тем более не связал бы ее с этой задачей.
Все так как ВЫ, УВАЖАЕМЫЕ и написали, все работает.
ОГРОМНОЕ СПАСИБО!!!
В жизни бы не вспомнил эту теорему Ферма, и тем более не связал бы ее с этой задачей.
Все так как ВЫ, УВАЖАЕМЫЕ и написали, все работает.
ОГРОМНОЕ СПАСИБО!!!
А решение такого уравнения никто не подскажет? 
x = ( y ^ 3 ) mod ( 2 ^ 160 )
Где:
x - известно, у - необходимо найти
x = ( y ^ 3 ) mod ( 2 ^ 160 )
Где:
x - известно, у - необходимо найти
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.