Как получить неизвестные значения учетом неупорядоченного списка ?

Кто-нибудь может мне помочь со следующей проблемой?

Я хочу найти некоторые значения $a_i,b_j$ (mod $N$ ), где $i=1,2,…,K, j=1,2,…,K$ (например, $K=6$ ), учитывая список значений $K^2$ которые соответствуют различиям $a_i-b_j\pmod N$ (например, $N=251$ ), не зная конкретного соответствующего отношения. Поскольку значения $a_i,b_j\pmod N$ не определены однозначно с учетом различий $a_i-b_j\pmod N$ , мы ищем любое допустимое присвоение значений.

Определенно, попытка каждой перестановки чисел $K^2$ в списке (всего $K^2!$ Возможных случаев), а затем решение модульных уравнений с $a_i,b_j$ в качестве переменных невозможно.

Фактически эта проблема возникает в статье о криптоанализе в ранней версии схемы подписи NTRU ( http://eprint.iacr.org/2001/005 ). Однако автор написал только одно предложение «Простой алгоритм возврата находит одно решение…» (в разделе 3.3), и поэтому кто-нибудь может дать больше объяснений? Более того, автор также упомянул, что «каждый круговой сдвиг $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ или обмен $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ приводит к тому же шаблону $a_i-b_j\mod N$ ”, и полезно ли это утверждение?

Вот предложение для и . Нам дан список . Начните с принятия одного из них без потери общности . Без ограничения общности , и мы получим значение . Теперь возьмите другой и надеемся, что он имеет форму (это происходит с вероятностью ), и выведите .K = 6 N = 251 a i - b $K = 6$$N = 251$( модН ) 1 - б 1 б 1 = 0 1 2 - б 1 5 / 35 = 1 / 7 $a_i - b_j \pmod{N}$$a_1-b_1$$b_1=0$$a_1$$a_2-b_1$$5/35 = 1/7$$a_2$

На этом этапе мы знаем . Наша следующая цель - найти для . Для каждого кандидата , если тогда также должны быть в списке. Если , то вероятность того, что также присутствует в списке, составляет примерно . Так что если мы найдем кандидата для которого также есть в списке, то, вероятно, . Таким образом, мы можем восстановить с некоторой уверенностью.a 1 , a 2 , b 1 a 1 - b j j ≠ 1 a i - b j i = 1 ( a i - b j ) + ( a 2 - a 1 ) = a 2 - b j i ≠ 1 ( a i - b j ) + ( a 2 - $a_1,a_2,b_1$$a_1-b_j$$j \neq 1$$a_i-b_j$$i=1$$(a_i-b_j)+(a_2-a_1)=a_2-b_j$$i \neq 1$ 1 ) 33 /$(a_i-b_j)+(a_2-a_1)$$33/251$ я - б J ( я - Ь J ) + ( 2 - 1 ) я = 1 б $a_i-b_j$$(a_i-b_j)+(a_2-a_1)$$i=1$$b_2$

На этом этапе мы знаем . Таким же образом, как мы восстановили , мы можем восстановить с достаточной уверенностью. Затем мы можем восстановить путем поиска кандидата для которого и оба находятся в списке. Потому что у нас есть еще с, наша вероятность отказа идет значительно вниз. Продолжаем и находим .a 1 , a 2 , b 1 , b 2 b 2 a 3 b 3 a i - b j ( a i - b j ) + ( a 2 - a 1 ) ( a i - b j ) + ( a 3 - a 1 ) а б 3 , а 4 , б $a_1,a_2,b_1,b_2$$b_2$$a_3$$b_3$$a_i-b_j$$(a_i-b_j)+(a_2-a_1)$$(a_i-b_j)+(a_3-a_1)$$a$$b_3,a_4,b_4,a_5,b_6,a_6,b_6$

В любой точке этого алгоритма мы могли догадаться, что что-то не так, и это в конечном итоге приведет к противоречию (скажем, в какой-то момент нет подходящего кандидата ). Затем мы возвращаемся назад и пробуем другую возможность; если мы исчерпали все возможности, мы снова вернемся назад и попробуем другую возможность (для другой стадии алгоритма); и так далее.$a_i-b_j$

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

Обновление : приведенное ниже описание относится к другой задаче (в которой у вас есть все попарные расстояния в наборе, а не попарные расстояния между двумя различными наборами). Я все равно оставлю это, так как это тесно связано.

Эта проблема называется проблемой кольцевой дороги и является частным случаем общей проблемы вложения тора. Это также тесно связано с проблемой магистрали, в которой различия расстояний являются абсолютными (не по модулю некоторого числа).$d$

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

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

Предположим, у нас есть четыре различия: , , , которые возникают как парные различия между двумя 's и двумя ' s. Назовите это квартет различий. Обратите внимание, что у нас нетривиальные отношения:$a_1-b_1$$a_1-b_2$$a_2-b_1$$a_2-b_2$$a$$b$

Вы можете попытаться использовать это отношение для выявления потенциальных квартетов из списка . Например, выберите четыре различия из списка; если они не удовлетворяют вышеуказанным отношениям, то они определенно не возникают из структуры квартета; если они удовлетворяют отношения, они могут возникнуть из квартета.$K^2$

Есть много способов взять вещи отсюда, но я подозреваю, что этого будет достаточно.

Я особенно подозреваю, что для вашего примера настройки параметров проблема будет довольно простой, потому что вышеописанный тест для распознавания квартета, вероятно, не будет иметь слишком много ложных срабатываний. Наш из всех способов выбора 4 отличий из списка, будет квартета (которые будут удовлетворять соотношению), а остальные являются не квартетами (которые удовлетворяют связь с вероятностью , эвристически). Поэтому мы ожидаем увидеть примерно ложных срабатываний, то есть 4 кортежа, которые проходят тест, даже если они не являются квартетами. Для ваших параметров это означает, что у нас есть 225 квартетов и${K^2 \choose 4}$${K \choose 2}^2$$1/N$$({K^2 \choose 4}-{K \choose 2}^2)/N$$(58905-225)/251 \approx 234$другие ложные срабатывания; так что около половины 4-х кортежей, прошедших тест, на самом деле являются квартетами. Это означает, что приведенный выше тест является довольно хорошим способом распознавания квартетов. Как только вы сможете распознать квартеты, вы действительно сможете отправиться в город, чтобы восстановить структуру списка различий.

Вот другой подход, основанный на итеративном поиске чисел, которые не могут появляться среди . Назовем множество Чрезмерно аппроксимацию «S , если мы знаем , что . Точно так же, является overapproximation из «ы , если мы знаем , что . Очевидно, что чем меньше , тем более полезно это по-приближение, и то же самое относится и к . Мой подход основан на итеративном уточнении этих чрезмерных аппроксимаций, т.е. итеративном уменьшении размера этих множеств (поскольку мы исключаем все больше и больше значений как невозможных).{ a 1 , … , a 6 } A a { a 1 , … , a 6 } ⊆ A B b { b 1 , … , b 6 } ⊆ B A $\{a_1,\dots,a_6\}$$A$$a$$\{a_1,\dots,a_6\} \subseteq A$$B$$b$$\{b_1,\dots,b_6\} \subseteq B$$A$$B$

Ядром этого подхода является метод уточнения : с учетом чрезмерного приближения для 's и чрезмерного приближения для ' s найти новое избыточное приближение для ', такое, что . В частности, обычно будет меньше, чем , так что это позволяет уточнить чрезмерное приближение для .A a B b A ∗ a A ∗ ⊊ A A ∗ A $A$$a$$B$$b$$A^*$$a$$A^* \subsetneq A$$A^*$$A$$a$

С помощью симметрии, по существу, тот же трюк позволит нам уточнить наше чрезмерное приближение для : s: с учетом избыточного приближения для и s и чрезмерного приближения для , это создаст новое -приближение для .b A a B b B ∗$b$$A$$a$$B$$b$$B^*$$b$

Итак, позвольте мне рассказать вам, как сделать уточнение, тогда я соберу все вместе, чтобы получить полный алгоритм для этой проблемы. В дальнейшем пусть обозначает множество множеств разностей, т. ; мы сосредоточимся на поиске дорабатываться приближения , учитывая .D D = { a i - b j : 1 ≤ i , j ≤ 6 } A ∗ A , $D$$D=\{a_i-b_j:1 \le i,j \le 6\}$$A^*$$A,B$

Как рассчитать уточнение. Рассмотрим одну разность . Рассмотрим множество . Основываясь на наших знаниях о том, что является чрезмерным приближением , мы знаем, что хотя бы один элемент из должен быть элементом . Таким образом, мы можем рассматривать каждый из элементов в , как «предложение» для ряда , чтобы возможно включить в . Итак, давайте рассмотрим все различия и, для каждого, определим, какие числа «предложены» .d ∈ D d + B = { d + y : y ∈ B } B b d + B { a 1 , … , a 6 } d + B A d ∈ D $d \in D$$d+B=\{d+y : y \in B\}$$B$$b$$d+B$$\{a_1,\dots,a_6\}$$d+B$$A$$d \in D$$d$

Теперь я собираюсь заметить, что число обязательно будет предложено как минимум 6 раз во время этого процесса. Почему? Поскольку различие в , и когда мы его обработаем, будет одним из предложенных чисел (поскольку мы гарантируем, что , обязательно включает ). Точно так же разница появляется где-то в , и это заставит быть предложенным снова. Таким образом, мы видим, что правильное значение будет предложено как минимум 6 раз. То же самое верно для иa 1 a 1 - b 1 D a 1 b 1 ∈ B ( a 1 - b 1 ) + B a 1 a 1 - b 2 D a 1 a 1 a 2 a $a_1$$a_1-b_1$$D$$a_1$$b_1 \in B$$(a_1-b_1)+B$$a_1$$a_1-b_2$$D$$a_1$$a_1$$a_2$$a_3$, и так далее.

Итак, пусть будет набором чисел , которые были предложены как минимум 6 раз. Это, безусловно, является чрезмерным приближением , согласно приведенным выше комментариям.A ∗ a ∗$A^*$$a^*$$a$

В качестве оптимизации, мы можем отфильтровать все предложения, которые не присутствуют в сразу: другими словами, мы можем рассматривать разность как предполагающее все значения . Это гарантирует , что мы будем иметь . Мы надеемся, что строго меньше, чем ; никаких гарантий, но если все пойдет хорошо, возможно, так и будет.A d ( d + B ) ∩ A A ∗ ⊆ A A ∗$A$$d$$(d+B)\cap A$$A^* \subseteq A$$A^*$$A$

Собирая это вместе, алгоритм для уточнения для получения выглядит следующим образом:A , B A $A,B$$A^*$

1. Пусть . Это множество предложений.$S = \cup_{d \in D} (d+B)\cap A$

2. Подсчитайте , сколько раз появляется каждое значение . Пусть множество значений , которые появляются по крайней мере 6 раз в . (Это может быть осуществлено эффективно путем создания массива из 251 первоначально, первоначально все равен нуля, и каждый раз , когда число предполагается, вы увеличиваете , в конце концов вы несетесь через ищем элементы , которые имеют значение 6 или больше)S A ∗ S a s a [ s ] $S$$A^*$$S$$a$$s$$a[s]$$a$

Подобный метод может быть построен, чтобы уточнить A , B, чтобы получить B ∗ . Вы в основном обратные вещи выше и флип некоторые признаки: например, вместо D + B , вы смотрите на - г + A .$A,B$$B^*$$d+B$$-d+A$

Как вычислить начальное чрезмерное приближение. Чтобы получить наше начальное чрезмерное приближение, одна идея состоит в том, чтобы предположить (wlog), что b 1 = 0 . Отсюда следует, что каждое значение a i должно появляться где-то среди D , поэтому список различий D можно использовать в качестве нашего начального чрезмерного приближения для a 's. К сожалению, это не дает нам очень полезного чрезмерного приближения для b .$b_1=0$$a_i$$D$$D$$a$$b$

Лучший подход состоит в том, чтобы дополнительно угадать значение одного из а . Другими словами, мы предполагаем (wlog), что b 1 = 0 , и используем A = D в качестве нашего начального чрезмерного приближения a 's. Тогда мы угадать, один из этих 36 значений действительно один из через -х, скажем , на 1 . Это дает нам чрезмерное приближение B = a 1 - D для b . Мы используем это начальное чрезмерное приближение A , $a$$b_1=0$$A=D$$a$$a$$a_1$$B=a_1-D$$b$$A,B$затем итеративно уточняйте его до сходимости и проверяйте, верен ли результат. Повторим до 36 раз, с 36 различных догадок в 1 (в среднем 6 догадок должно быть достаточно) , пока мы не находим тот , который работает.$a_1$

Полный алгоритм. Теперь у нас может быть полный алгоритм для вычисления a 1 , … , a 6 , b 1 , … , b 6 . По сути, мы выводим начальное избыточное приближение для A и B , а затем итеративно уточняем.$a_1,\dots,a_6,b_1,\dots,b_6$$A$$B$

1. Сделайте предположение: для каждого z ∈ D предположим, что a 1 = z . Сделайте следующее:$z \in D$$a_1=z$

   1. Начальное течение приближения: Определить A = D и B = г - D .$A=D$$B=z-D$

   2. Итеративное уточнение: неоднократно применять следующее до сходимости:

      • Уточните A , B, чтобы получить новое избыточное приближение B ∗ из b .$A,B$$B^*$$b$
      • Уточните A , B ∗, чтобы получить новое избыточное приближение A ∗ из a .$A,B^*$$A^*$$a$
      • Пусть A : = A ∗ и B : = B ∗ .$A:= A^*$$B:= B^*$

   3. Проверьте успешность: если каждый из наборов A , B имеет размер 6, проверьте, являются ли они допустимым решением проблемы. Если они есть, остановись. Если нет, продолжайте цикл по значениям-кандидатам z .$A,B$$z$

Анализ. Будет ли это работать? Сойдет ли он в конечном итоге на A = { a 1 , … , a 6 } и B = { b 1 , … , b 6 } , или застрянет, не решив полностью проблему? Лучший способ выяснить это, вероятно, проверить это. Однако, по вашим параметрам, да, я ожидаю, что это будет эффективно.$A=\{a_1,\dots,a_6\}$$B=\{b_1,\dots,b_6\}$

Если мы используем метод # 1, пока | A | , | Б | не слишком велики, эвристически я ожидаю, что размеры наборов будут монотонно уменьшаться. Рассмотрим выводе A * из A , B . Каждое различие d предполагает | Б | ценности; один из них правильный, а другой | Б | - 1 можно рассматривать (эвристически) как случайные числа. Если x - это число, которое не появляется среди a , то какова вероятность того, что оно выдержит фильтрацию и будет добавлено к $|A|,|B|$$A^*$$A,B$$d$$|B|$$|B|-1$$x$$a$∗ ? Ну, мы ожидаембудет предложено о ( | B | - 1 ) × 36 / 251 раз в общей сложности (в среднем, со стандартным отклонением около квадратного корня из этого). Если | Б | ≤ 36 , вероятность того, что неправильный x переживет фильтрацию, должна составлять примерно p = 0,4 или около того (используя нормальное приближение для бинома с коррекцией непрерывности). (Вероятность меньше, если | B | меньше; например, для | B |$A^*$$a$$(|B|-1) \times 36/251$$|B|\le 36$$x$$p=0.4$$|B|$30 , я ожидаю, что p ≈ 0,25 .) Я ожидаю, что размер A ∗ будет примерно равен p ( | A | - 6 ) + 6 , что строго улучшит чрезмерное приближение, поскольку оно строго меньше | A | , Например, если | A | = | Б | = 36 , то исходя из этой эвристики я ожидаю | A ∗ | ≈ 18 , что является большим улучшением по сравнению с | A $|B|=30$$p\approx 0.25$$A^*$$p (|A|-6) + 6$$|A|$$|A|=|B|=36$$|A^*|\approx 18$$|A|$,

Поэтому я прогнозирую, что время бега будет очень быстрым. Я ожидаю, что для сходимости будет достаточно 3-5 итераций уточнения, и, вероятно, достаточно около 6 предположений при z . Каждая операция уточнения включает, возможно, несколько тысяч операций чтения / записи в память, и мы делаем это, возможно, 20-30 раз. Итак, я ожидаю, что это будет очень быстро для указанных вами параметров. Тем не менее, единственный способ узнать наверняка - это попробовать и посмотреть, хорошо это работает или нет.$z$