Вопрос про Черный ящик

[Ales]

Ну да, можно ведь найти НОД $(2^{2049}-r_2,3^{2049}-r_3)$.

-- Чт май 13, 2010 13:48:58 --

Xaositect в сообщении #318865 писал(а):

Если неизвестна степень - то это дискретный логарифм.

Достаточно уметь находить дискретный логарифм, но точно ли необходимо?

-- Чт май 13, 2010 14:07:57 --

lel0lel в сообщении #318876 писал(а):

Ales в сообщении #318873 писал(а):

Интересно, кто-нибудь раньше задавал этот вопрос про черный ящик или нет?

Задача Йоста, обратная задача рассеяния.

Мне это ничего не говорит. В интернете тоже ничего не нашел про это. Не можете объяснить подробнее?
Это точно тот же вопрос, или это ассоциация - похожий вопрос?

-- Чт май 13, 2010 14:21:06 --

Ales в сообщении #318905 писал(а):

Ну да, можно ведь найти НОД .

А если степень будет $2^{100}+1$? Так уже не решить.

[Xaositect]

Ales в сообщении #318905 писал(а):

Цитата:

Ну да, можно ведь найти НОД .

А если степень будет $2^{100}+1$? Так уже не решить.

Тогда как я говорил, через квадраты.

[Ales]

Xaositect в сообщении #318924 писал(а):

Ales в сообщении #318905 писал(а):

Цитата:

Ну да, можно ведь найти НОД .

А если степень будет $2^{100}+1$? Так уже не решить.

Тогда как я говорил, через квадраты.

Понял. Здорово. Годится для любой степени.

[Pavlovsky]

Решение простое. Черный ящик кто то ведь сделал. Найти разработчика. А там по ситуации, либо пивом напоить либо паяльником... узнать конкретный вид функции.

[lel0lel]

Обратная задача рассеяния, когда у вас задан спектр падающего излучения, т.е. входные данные. Задан спектр рассеянной волны. Требуется найти возмущающий потенциал - тот алгоритм, который содержится в ящике. С линейными обратными задачами никаких проблем нет, некоторые нелинейные также сводятся к однозначно разрешимому интегральному уравнению первого рода.

[Ales]

lel0lel в сообщении #318950 писал(а):

Обратная задача рассеяния, когда у вас задан спектр падающего излучения, т.е. входные данные. Задан спектр рассеянной волны. Требуется найти возмущающий потенциал - тот алгоритм, который содержится в ящике. С линейными обратными задачами никаких проблем нет, некоторые нелинейные также сводятся к однозначно разрешимому интегральному уравнению первого рода.

Спасибо, понятно.
С линейными ясно как поступать: выбрать базис и разложить входные данные по базису.

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

-- Чт май 13, 2010 16:16:16 --

Добавлю, что сравнение функций по коду (два разных кода задают одну и ту же функцию или нет) - это известная задача P=?NP.

[Ales]

Кажется, я решил вопрос: нельзя найти, что внутри черного ящика.

Для любой последовательности наборов входящих данных можно построить функцию $f$, совпадающую на этих наборах с функцией из ящика и равную нулю на остальных наборах, а также функцию $g$, равную нулю на наших испытаниях и единице на остальных наборах.
Тогда любая функция вида $f \lor g \& h$ совпадает с функцией из ящика на последовательности испытаний.
Пусть мы построили некоторую функцию только по данным испытаний, тогда есть море функций удовлетворяющих этим испытаниям. Невероятно что мы нашли именно ту функцию, что было нужно.

Кстати, из этого можно сделать вывод: физика не верна.

[lel0lel]

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

"Физические понятия суть свободные творения человеческого разума, а не определены однозначно внешним миром, как это иногда может показаться. В нашем стремлении понять реальность мы отчасти подобны человеку, который хочет понять механизм закрытых часов. Он видит циферблат и движущиеся стрелки, даже слышит тиканье, но он не имеет средств открыть их корпус. Если он остроумен, он может нарисовать себе некую картину механизма, которая отвечала бы всему, что он наблюдает, но он никогда не может быть вполне уверен в том, что его картина единственная, которая могла бы объяснить его наблюдения. Он никогда не будет в состоянии сравнить свою картину с реальным механизмом, и он не может даже представить себе возможность или смысл такого сравнения. Но он, конечно, уверен в том, что, по мере того как возрастает его знание, его картина реальности становится все проще и проще и будет объяснять все более широкий ряд его чувственных восприятий. Он может также верить в существование идеального предела знаний и в то, что человеческий разум приближает этот предел. Этот идеальный предел он может назвать объективной истиной." Эволюция физики. Альберт Эйнштейн, Леопольд Инфельд.

[Xaositect]

Ales в сообщении #318816 писал(а):

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

lel0lel в сообщении #318982 писал(а):

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

Какие бесконечные последовательности? Какие гладкие отображения? Отображение самое что ни на есть дискретное.

[Ales]

lel0lel в сообщении #318982 писал(а):

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

К сожалению нельзя так делать: каждое испытание забирает реальное время (компьютерное).
Можно сделать миллион шагов, миллиард, но не $2^{1000}$.
И непрерывности в общем случае нет никакой.
К счастью, в физике хотя бы есть непрерывность, поэтому, например, механика работает.
А вот общая теория "всего" похоже недостижима.

-- Чт май 13, 2010 17:20:44 --

Xaositect в сообщении #318986 писал(а):

Какие бесконечные последовательности? Какие гладкие отображения? Отображение самое что ни на есть дискретное.

Конечно, с гладкими отображениями работа - не бей лежачего.
Нам бы их проблемы .

Самые сложные задачи - дискретные, вот где конь не валялся.

[eLectric]

А если ЧЯ с памятью и нет однозначной зависимости между входами и выходами?

[Xaositect]

eLectric в сообщении #319081 писал(а):

А если ЧЯ с памятью и нет однозначной зависимости между входами и выходами?

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

[Circiter]

2Ales
А что если статистику натравить на этот ящик? :)

[Ales]

Circiter в сообщении #319135 писал(а):

2Ales
А что если статистику натравить на этот ящик? :)

Статистика не поможет распознать функцию.

[Circiter]

2Ales

Цитата:

Статистика не поможет распознать функцию.

Зато можно получить другой ЧЯ, статистически "неотличимый" от первого и пользоваться им...