Оптимизированные базовые алгоритмы для вычисления сверхдлинных последовательностей аппаратного шифрования

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:51, 21 декабря 2015.
Improved Generic Algorithms for Hard Knapsacks
Improved Generic Algorithms for Hard Knapsacks.png
Авторы Anja Becker[@: 1],
Jean-Sebastien Coron[@: 2] and
Antoine Joux[@: 3]
Опубликован 2010 г.
Перевели Nikolay Morozov
Год перевода 2015 г.
Скачать оригинал


Содержание

Аннотация. На конференции Eurocrypt 2010 Хаугрэйв-Грэхем и Жу описали алгоритм вычисления сверхдлинных последовательностей аппаратного шифрования с плотностью, близкой к 1 во времени и памяти , чем усовершенствовали алгоритм Шамира и Шроппеля, разработанный 30 лет назад. В данной статье мы детализируем технологию Хаугрэйв-Грэхема и Жу для получения алгоритма со временем работы, уменьшенным до . Его реализация мы демонстрирует применимость данного метода. Другая задача состоит в уменьшении требуемой памяти. Мы описываем алгоритм для постоянной памяти, основанный на нахождении цикла со временем ; также мы демонстрируем компромисс времени и памяти.

Введение

Задача сверхдлинной последовательности. При условии, что список n позитивных целых чисел (a1,a2,...,an) и другое позитивное число S, рассматривается в формуле: , (1) где , задача сверхдлинной последовательности состоит в восстановлении коэффициентов . Вектор является решением задачи сверхдлинной последовательности. Общеизвестно, что решающая версия задачи сверхдлинной последовательности является НП-полной [1]. Первая криптосистема, основанная на задаче сверхдлинной последовательности, была реализована Меркелем и Хельманом [2] в 1978 году, после чего ее взлом был осуществлен Шамиром [3] с применением решетчатого разрешения. Применительно к задачам с хаотичными сверхдлинными последовательностями можно использовать атаку Лагариаса-Одлыжко [4] с плотностью до d < 0.94, задавая оракулу решение кратчайшей векторной проблемы (SVP) в решетках; плотность сверхдлинной последовательности определяется как:

Атака Лагариаса-Одлыжко была в дальнейшем усовершенствована Костером и со-авторами [5] до плотности d < 0.94. Поскольку известно, что решение SVP является NP-трудным [6], на практике самый короткий вектор оракула замещается алгоритмом решетчатого разрешения, таким как LLL [7] или BKZ [8].

Алгоритм Шроппеля-Шамира. Применительно к сверхдлинной последовательности с плотностью, близкой к 1, алгоритмы решетчатого разрешения не является эффективным. До 2009 года самым лучшим алгоритмом для таких сверхдлинных последовательностей аппаратного шифрования был алгоритм Шроппеля и Шамира [9] с временной сложностью и памятью . Время выполнения алгоритма такое же, как и в прямом алгоритме с пересечением в середине, но с меньшей требуемой памятью , вместо . Недостатком алгоритма Шроппеля-Шамира является то, что он требует сложной структуры данных, такой, как сбалансированные деревья, что на практике может быть трудноосуществимым. Более простой, но эвристический вариант алгоритма Шроппеля-Шамира с такой же сложностью по времени и памяти был описан в источнике [10]; мы вернемся к нему в Разделе 2.1. Также мы вспомним способы решения задач с неравновесной сверхдлинной последовательностью, в которой вес Хемминга вектора коэффициентов может быть намного меньше, чем .

Алгоритм Хаугрэйв-Грэхема-Жу. На конференции Eurocrypt 2010 Хаугрэйв-Грэхем и Жу представили более эффективный алгоритм [10] для вычисления сверхдлинных последовательностей аппаратного шифрования. Тогда как в алгоритме Шроппеля-Шамира последовательность делится на две половины без перекрытия, новый алгоритм допускает перекрытия, что дает больше свободы действий. Благодаря этому, время работы алгоритма можно уменьшить до , при этом размер памяти держится на рационально низком уровне: . В Разделе 2.2 мы вернемся к алгоритму Хаугрэйв-Грэхема-Жу.

Наш вклад. Основным вкладом нашей работы является детализация метода Хаугрэйв-Грэхема-Жу, которая привела нас к получению нового алгоритма с уменьшением времени работы до . Последовательность делится на две половины с возможностью перекрытия, как в алгоритме Хаугрэйв-Грэхема-Жу, при этом набор возможных коэффициентов увеличивается с {0, 1} до {−1, 0,+1}. Это означает, что коэффициент в первой половине можно компенсировать коэффициентом во второй половине, при этом в золотом решении коэффициент является результатом вычисления: . Добавление (нескольких) коэффициентов -1 обеспечивает дополнительную свободу действий, что позволяет снова уменьшить время работы алгоритма; наш новый алгоритм представлен в Разделе 3. Мы показываем применимость метода путем его реализации для n = 80 и n = 96. Тем не менее, для n = 96 наш алгоритм менее эффективен, чем наше улучшение алгоритма Хаугрэйв-Грэхема-Жу. Другой проблемой в решении задач со сверхдлинными последовательностями является уменьшение требуемой памяти. Сначала описан простой алгоритм с постоянной памятью, основанный на нахождении цикла со временем работы . Нами продемонстрирован способ оптимизации данного алгоритма до значения времени работы , для чего все-таки требуется постоянная память, но используется метод Хаугрэйв-Грэхема-Жу. В завершение, мы описываем компромисс времени и памяти для алгоритма Шроппеля-Шамира с уменьшением требуемой памяти до . Эти алгоритмы описаны в Разделе 4.

Существующие алгоритмы

Эта часть описывает алгоритмы Шроппеля-Шамира [9] и Хаугрэйв-Грэхема-Жу [10], чтобы читатель был знаком с методами, и было легче понять алгоритм, предложенный ниже.

Алгоритм Шроппеля-Шамира

Мы реализуем алгоритм Шроппеля-Шамира [9] в более простом эвристическом варианте, описанном в источнике [10]. Считаем сверхдлинную последовательность такой, как в формуле (1), а для простоты предположим, что кратно 4. Записываем сумму последовательности как:

где каждое значение σi является последовательностью из n/4 элементов, что выражается как:

, , , (2)

Делаем предположение о средней величине из бит, которая приводит к выаражениям: .

Два уравнения решаем отдельно и объединяем результат. Точнее, сначала составляем отсортированный список всех возможных значений для . Затем для каждого возможного значения используем отсортированный список для нахождения всех значений , таким образом, чтобы . В результате этого получаем список значений последовательности , при которых ; размер списка эвристически становится , и он может быть построен во времени . Мы построили список значений сверхдлинной последовательности таким образом, что . В результате мы находим столкновение двух элементов и между двумя списками и соответственно. Для правильного определения значения мы установили элементы таким образом, что , решая тем самым задачу сверхдлинной последовательности. Время, необходимое для построения двух списков и равно . Затем при сортировке этих двух списков можно найти столкновение во времени . Поскольку нам необходимо предположить величину , равную значению бит, общее время работы алгоритма будет равно , а требуемая память - .

Рис. 1. Иллюстрация модульного варианта Шроппеля-Шамира .

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

Как показано в источнике [10], это преимущество можно адаптировать следующим образом: вместо учета всех возможных последовательностей элементов , мы учитываем только последовательности с точным весом Хемминга (предположив, что делится на 4). Обратите внимание, что если правильное решение не вполне уравновешено между четырьмя четвертями, решение будет потеряно. Например, если вес Хэмминга решения в первой четверти будет , а во второй - , следовательно, решение упущено. Эта задача легко решается путем перестановки порядка элементов в последовательностях до тех пор, пока вес Хемминга каждой из четвертей не будет равен . Как разъяснено в источнике [10], ожидаемое число требуемых повторений - многочлен . Поэтому данное изменение не преобразовывает значение порядка чисел во времени работы алгоритма.

Для размер списков и становится равным , где:

.

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

Алгоритм Хаугрэйв-Грэхема-Жу

Рассмотрим сверхдлинную последовательность (1). Для простоты снова предположим, что n кратно четырем, а также то, что вес Хемминга коэффициентов равен . Основная идея решения , предложенная Хаугрэйв-Грэхемом и Жу [10], состоит в разбитии сверхдлинной последовательности на две составляющие последовательности размерности и веса Хемминга . Другими словами, записываем как сумму двух составляющих последовательностей с весом Хемминга , выбранным из числа n элементов последовательности:

(3)

где . Очевидно, что комбинация двух решений и обеспечивает решение исходной последовательности, когда между этими двумя решениями нет перекрытия. Другими словами, мы представляем любое значение xi в виде двоичного набора элементов , заменяя 0 - (0, 0) и 1 - (1, 0) или (0, 1) соответственно. Вследствие этого единственное решение исходной задачи сверхдлинной последовательностью раскладывается на множество различных. Это используется для уменьшения суммарного времени работы алгоритма, как описано далее. Выбираем модуль М, случайный элемент , затем рассматриваем разбиение следующим образом:

and

Поскольку и являются последовательностями с весом Хемминга над n элементами, ожидаемое число решений каждой из этих двух модулярных составляющих последовательностей равно

Предполагая, что списки решений двух составляющих последовательности могут быть получены очень результативно (во времени ), остается скомбинировать частные решения и найти решение исходной последовательности. То есть, мы ищем коллизию между значениями и - для всех y и z в двух списках решений. Поскольку ожидаемое число таких коллизий невелико, это можно выполнить за . Чтобы минимизировать суммарное время работы алгоритма, значение М задается максимально большим. Точнее, значение М подбирается как число, приближенное к числу разбиений исходного решения на два решения двух составляющих последовательности, например, . При таких предполагаемых условиях время прохождения задания было бы уменьшено до .

Однако в применении данного подхода существует несколько технических различий. Во-первых, присутствует экспоненциально малое число неверных весовых значений (, .., ), для которых алгоритм не эффективен. Во-вторых, предположение, что список решений каждой составляющей последовательности может быть получен за время , достаточно строгое и его сложно соблюсти. В качестве следствия, [10] предлагает мене эффективные алгоритмы, которые достигают более низкой границы, по более понятны.

В источнике [10] описан эвристический алгоритм, подтвержденный реализацией, и утверждается, что он эффективен при вычислении времени работы алгоритма . Однако Мэй и Мюрер недавно обнаружили ошибку в анализе данного алгоритма [11]. Проблема возникает при слиянии двух частей последовательности в одно общее решение. Два списка и частных решений сравнимой длины, скажем, L, соединяются в список глобального решения, который удовлетворяет дополнительному модульному ограничению по модулю M. Предполагаемый размер результирующего списка . Что касается логарифмических факторов, в статье [10] говорится, что сложность этого процесса слияния равняется . Тем не менее, данный способ не принимает во внимание тот факт, что слияние включает в себя процесс фильтрации. Процесс фильтрации исключает решения, которые возникают при слиянии двух перекрывающихся частных решений. При учете этого, получаем сложность , где - размер среднего списка решения до фильтрации. Предполагаемое значение равняется . Учитывая это, Мэй и Маурер продемонстрировали, что асимптотическое время прохождения задания алгоритма Хаугрэйв-Грэхема-Жу в действительности равно .

Новый алгоритм с оптимизированной временной сложностью

Мы представляем доработку алгоритма [10], упомянутого в Разделе 2.2, чтобы в дальнейшем улучшить его временную сложность. В Разделе 3.1 мы предположим, что сверхдлинные последовательности могут быть решены продуктивно, откуда получим нижнюю границу сложности нового алгоритма. Тем не менее, это предположение слишком серьезное, и мы не знаем, как достичь этой нижней границы; следовательно, улучшение носит чисто теоретический характер. В Разделе 3.3 мы описываем конкретный алгоритм, который принимает во внимание действительное время работы алгоритма нижних границ и достигает лучшего ассимптотического времени, чем предыдущие подходы.

Теоретические улучшения

Наша основная идея состоит в повышении эффективности алгоритма [10] посредством большего числа реализаций решения исходной последовательности. Вместо разбиения исходного решения на два двоичных вектора коэффициента веса n/4, мы рассматриваем разбиения, содержащие числа 0, 1 и -1. Точнее, мы подбираем параметр α и отыскиваем разбиения, содержащие (1/4+ α)n 1 и αn -1. То есть, мы разбиваем единицы исходного решения на пары (0, 1) или (1, 0), как и ранее, а также нули на пары (0, 0), (1, -1) или (-1, 1). Число таких разбиений равно

.

Как описано в Разделе 2.2, мы выбираем модуль , случайное значение R модуля M и отыскиваем решения двух составляющих последовательности

and ,

где y и z содержат (1/4+ α)n единиц и αn -1 каждое. Ожидаемое число решений каждой из этих новообразованных модулярных составляющих последовательности равно

. <.center> Используя: <center>

где:

мы получаем:

Предполагая, что составление списков и отыскание коллизий может выполняться за время и при минимизируя α, мы получаем временную сложность для α ≈ 0.103.

Этот анализ показывает, что добавление большего числа реализаций исходного решения потенциально может способствовать оптимизации алгоритмов. Однако для отыскания такого алгоритма нужно преодолеть много препятствий. Первое препятствие состоит в том, что размер модуля не должен превышать размер элементов последовательности. Безусловно, мы хотим, чтобы после уменьшения модуля последовательность имела свойства случайной последовательности, что не будет достигнуто, если превышает по размеру элементы исходной последовательности. Поэтому нам нужно соблюсти . Доведя в этих условиях до оптимума, мы получаем и .

В продолжении этой статьи мы более подробно разбираем сложность приведенных ниже уравнений и показываем, что построить алгоритмы, основанные на этой новой идее, возможно с лучшей асимптотической временной сложностью, чем в [10] .

Основная структурная единица

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

.

Для решения этой задачи используем классический алгоритм [12], описание которого представлено в псевдокоде Алгоритма 1.

Алгоритм 1. Вычисление списка

Сортируем списки и (увеличивая размер значений модуля );

Пусть Искомое значение ;

Пусть и ; Пока i< |La| and j ≥ 0

Пусть Сумма ;

если Сумма < Искомое значение, то увеличить ;

если Сумма > Искомое значение, то уменьшить ;

если Сумма = Искомое значение, то

Пусть ;

пока - увеличить ;

Пусть ;

пока и - уменьшить ;

для до

для до do Присоединить к

end

Пусть и ;

еnd

end

Пусть Искомое значение ;

Пусть и ;

Повторить приведенный выше цикл с новым искомым значением;


Сложность Алгоритма 1 равняется . Более того, предполагая случайное распределение значений модуля M исходных списков, ожидаемый размер равен . Однако, в целом, гарантировать это невозможно.

Используя небольшое изменение Алгоритма 1, также возможно с учетом и , в совокупности с искомым целым числом R, построить множество:

Различия состоят лишь в том, что списки мы сортируем по значению (не по модулярным значениям), затем проходим цикл с единственным заданным искомым значением R (вместо двух).

Разработка конкретного алгоритма

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

Вместо этого мы используем идею разбиения последовательности на две составляющие последовательности несколько раз. Точнее, мы реализуем три уровня разбиения; см. Рис. 2 в качестве иллюстрации. Первое разбиение следует за методом, описанным в Разделе 3.1, с другим (меньшим) вариантом величины α, что означает пропорцию чисел -1, добавленных с каждой стороны. На втором или среднем уровне проводим разбиение каждой составляющей последовательности из первого уровня на два. Также в разбиения добавляем новые числа -1. Количество дополнительных -1 для каждой из четырех составляющих последовательности на среднем уровне контролируется новым параметром β. На последнем уровне используем параметр для обозначения пропорции дополнительных -1 в составляющих последовательности. Используем параметр γ, чтобы добавить дополнительные -1 в подпоследовательности.


Золотое решение ,

Соответствующее сумме

Рис. 2. Итерационное разбиение в трех этапах.  : частичная сумма,  : искомое значение, : модуль,  : пропорция из дополнительных -1. 

Система представления чисел. Для обозначения векторов коэффициентов каждой составляющей последовательности мы используем другие буквы греческого алфавита ( или ). В исходной последовательности мы использовали букву . На первом уровне разбиения мы теперь используем и для обозначения векторов коэффициентов двух составляющих последовательности. На среднем уровне мы выбираем обозначения от до . На самом нижнем уровне используем буквы от до . Затем задаем, что означает встречаемость в векторе коэффициента . Для последовательности из n элементов получаем:

Мы всегда имеем . Поскольку все эти числа должны быть округлены до целых чисел для конкретного момента последовательности, в вышеуказанных формулах записываем вместо =. Для каждого из векторов коэффициента вводим соответствующую частичную сумму:

Для контроля размера списков решений, образуемого на каждом уровне разбиения, мы вводим модуль и искомые значения для каждой из составляющих последовательности. Обозначаем модуль, соответствующий самому нижнему уровню, как , вводим 7 случайных значений (для ) и задаем, что . Затем решаем восемь модулярных составляющих последовательности:

для .

Вводим обозначение для списка решений каждой из данных составляющих последовательностей. Рис. 2 отображает декомпозицию, а рис. 3 показывает слияние списков до тех пор, пока не найдется золотое решение в последнем списке .

Основной принцип и модулярные ограничения. Для построения решений на среднем уровне k мы рассматриваем суммы из двух частных решений, взятых из двух смежных списков и , содержащих решения последнего уровня. При построении видим, что:

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

Для первого уровня мы действуем аналогичным образом, добавляя частные решения из списков и . Очевидно, что образованные суммы уже содержат определенные значения модулей и . Снова вводим модуль math>\ M_{\nu} ~ \, \! </math>, случайное значение и задаем, что с целью уменьшения размера списков.

В конечном итоге (предположительно единственное) решение исходной сверхдлинной последовательности отыскивается посредством поиска коллизии формулы с и . На Рисунке 2 этот метод проиллюстрирован.

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

Детали алгоритма. Восемь списков можно построить при помощи прямой адаптации простого парадокса дней рождения. Достаточно разбить n элементов на два произвольных подмножества размером n/2 и предположить, что числа 1 и -1 равномерно распределены между двумя половинами. Как и в случае с двоичными векторами коэффициента, вероятность этого обратно пропорциональна многочлену в n. Поэтому, путем многократного полиномиального повторения мы восстанавливаем все с преобладающей вероятностью. Предполагая, что элементы в списке являются случайными по модулю , ожидаемый размер списка равен:

,

где является мультиномиальным коэффициентом, вычисляющим количество способов выбора чисел 1, чисел -1 и чисел 0 среди n элементов. Поскольку количество способов выбора чисел 1, чисел -1 и чисел 0 среди элементов n/2 равно для большого значения n, время прохождения задания время выполнения каждого списка является ( ).

На среднем уровне ожидаемый размер списка имеет верхнее ограничение, определяемое формулой:

.

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

Для построения этих списков мы сопоставляем значения из списков и с учетом модуля при помощи Алгоритма 1 из Раздела 3.2. Задаем, что обозначает образуемый список. Затем отбрасываем неподходящие решения из списка для выведения . Мы утверждаем, что решение является неподходящим, когда вектор содержит числа 2 или -2 и/или не содержит числа 1, -1 и 0, заданные и . Согласно Разд. 3.2, затратность данного этапа максимальная ( ).

Продолжая в том же направлении, задаем верхнее ограничение ожидаемого размера списка :

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

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

Для оценки размера списка вычисляем количество ожидаемых решений в модулярно объединенном модуле, многочлен которого наиболее близок к . При этом размер списка оценивается выше, так как несколько легче отыскать модуль решения последовательности при этом значении, нежели решение последовательности на основе целых чисел. Находим возможное значение, равное:

.

Если содержит по меньшей мере одно подходящее решение, мы получаем решение исходной задачи сверхдлинной последовательности.

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

,

,

.

Обозначение в многочленах, представленных выше, указывает на количество оставшихся элементов (соответствующих числам 0) после определения чисел 1 и -1, введенных для разбиения множества 0 из низшего уровня.

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

Предполагая, что размер каждого списка близок к его ожидаемому значению (см. Раздел 3.5), ожидаемое время прохождения работы равно:

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

.

В конечном итоге, учитывать также необходимо еще один дополнительный и очень важный параметр – вероятность успеха , взятый на основе возможных случайных вариантов значений Этот параметр достаточно неоднозначен при вычислении, поскольку он изменяется в зависимости от исходной последовательности, которую мы решаем. В качестве иллюстрации рассмотрим сверхдлинную последовательность, элементы которой равны 0. Очевидно, что если все произвольные значения не выбраны равными 0, алгоритм не может дать результат. Вследствие этого, в данном случае вероятность успеха очень низкая. Существуют и многие другие неблагоприятные последовательности; однако для случайной последовательности прогнозируемая вероятность успеха не является слишком низкой (для ознакомления см. Раздел 3.4).

Численные результаты анализа сложности. Минимизация ожидаемого времени работы дает такой результат:

.

С этими значениями получаем следующее:

и .

Видим, что сложность и по времени, и по памяти равны .

Тем не менее, следует отметить, что слишком мала для любой достижимой последовательности длины n, число -1, добавленных на последнем уровне на практике будет равно нулю. Таким образом, чтобы улучшить практический выбор чисел -1 на высших уровнях, лучше применять минимизацию с добавлением константы . Что приведет к альтернативным значениям:

.

При этих значениях получим:

и .

Также можем отметить, что при выборе мы восстанавливаем временную сложность заданную Мэем и Мюрером [11] для алгоритма [10]. Однако в нашем случае сложность памяти также равна которая предвещает возможность оптимизации нашего алгоритма в этом отношении. В полной версии работы [13] мы также рассматриваем пример неуравновешенной последовательности и возможные варианты детализации.

Сложность для несбалансированного случая. Мы также проанализировали сложность для -несбалансированных последовательностей. На рис.4 показано, что сложность уменьшается, когда вес последовательности меньше 0.5. Для , больших 0.5, сложность возрастает. В этом случае лучше использовать добавочную последовательность.

Расширения. Для дальнейшего улучшения временной сложности решения последовательностей мы можем сделать несколько улучшений нашего нового алгоритма. Во-первых, можно добавить больше уровней декомпозиции (на 16 или более подпоследовательностей). Тем не менее, наши попытки построить алгоритм из четырех уровней не смогли побить трехуровневый алгоритм.

Рис. 4. Экспонента сложности для несбалансированных последовательностей.

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

Анализ вероятности успеха

Для анализа вероятности успеха целесообразно взять за основу рис. 2. Начинаем с неизвестного, но постоянного золотого решения сверхдлинной последовательности, разбиение которой мы намереваемся произвести семикратно. (На каждом этапе мы выражаем числа 0, 1 и -1 текущего вектора коэффициента набором из чисел (), где .) Для каждого из семи разбиений мы вводим модуль модулярного ограничения, являющийся числом, близким к суммарному количеству разбиений. Например, во время разбиения высшего уровня мы устанавливаем, что сумма левой стороны после разбиения должна соответствовать по модулю по модулю , а также по модулю . Поскольку три модуля являются взаимно простыми, это равнозначно простому определению модуля значения . Каждое из трех разбиений считается успешным, если текущее золотое решение допускает, по меньшей мере, один способ разбиения, удовлетворяющий модулярному ограничению. В этом случае мы сосредотачиваемся на одном из допустимых решений, для которого отыскиваем разбиение в более низком уровне. Установление решения на левой стороне также определяет решение правой стороны.

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

Рис. 2. Совокупное количество сверхдлинных последовательностей (до миллиона) с числом не отысканных значений, меньшим, чем заданное.

Абсолютно случайная эвристическая модель. Один из подходов к анализу вероятности успеха отдельного разбиения состоит в предположении, что для каждого из возможных разбиений образуемая модулярная сумма имеет случайное значение. Мы уже знаем, что существуют последовательности, для которых это предположение не действует, как продемонстрировано в примере со всеми нулями. Оно истинно для большого количества случайных последовательностей, однако для последующего анализа это является эффективным ориентиром. Для упрощения задачи предположим, что число возможных разбиений равно модулю для большого множества случайных последовательностей.

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

Испытываемые характеристики разбиений.В Разделе 5.1 мы описываем реализацию нашего алгоритма на сверхдлинной последовательности размером 80 бит. Для лучшего понимания поведения данной реализации целесообразно определить вероятность успеха каждого разбиения. Разбиение происходит в три уровня. На верхнем уровне для уравновешенного золотого решения с 40 нулями и 40 единицами должно быть разбито на два частичных решения с 22 единицами и двумя -1 каждое. На среднем уровне золотое решение с 22 единицами и двумя -1 предстоит разложить на два частичных решения с 12 единицами и двумя -1. В конечном итоге, на нижнем уровне, раскладываем 12 единиц и две -1 дважды по 6 единиц и однократно по -1.

На верхнем уровне количество возможных разбиений золотого решения превышает . В результате отсутствует возможность проведения экспериментальной статистики модулярных значений в таком большом множестве. На среднем уровне количество разбиений превышает . Следовательно, у нас есть возможность провести статистический анализ модулярных значений, но выполнение большого числа исследований для статистического анализа модулярных значений – весьма громоздкий процесс. На самом нижнем уровне количество разбиений золотого решения равно . Этого недостаточно для существенного статистического исследования, и, в частности, для изучения компонентов не отысканных модулярных значений (в зависимости от случайного выбора 14 элементов последовательности с 12 единицами и двумя -1, подлежащих разбиению). Значение модуля, используемого в данном эксперименте, равно 1847, что является простым числом, наиболее близким к 1848.

Во время нашего эксперимента мы составили один миллион модулярных составляющих последовательности из 14 случайно выбранных значений по модулю 1847. Среди этих значений 12 элементов соответствуют сложению, а 2 – вычитанию. Из этого множества мы вычислили (в ) все из 1847 значений, которые могут быть получены путем суммирования 6 из 12 элементов сложения и вычета одного из элементов вычитания. В каждом эксперименте мы вычислили число не найденных значений; результаты представлены на рис. 5. На вертикальной оси мы показали общее количество последовательностей, при решении которых x или менее значений отыскать не удается. Для возможности сравнения с абсолютно случайной моделью мы показываем такую же кривую, вычисленную для миллиона экспериментов, в которых выбираются 1848 случайных чисел по модулю 1847. В частности, на этом графике мы видим, что для 99.99% выстроенных нами случайных последовательностей доля не отысканных значений не превышает 2/3. Это означает, что в эксперименте вероятность успеха разбиения на самом низком уровне достигает по меньшей мере 1/3 для большей части последовательностей. При условии независимости между вероятностью успеха семи разбиений и аналогичными характеристиками трех уровней, мы делаем вывод, что для 99.93% случайных последовательностей среднее число повторений является достаточным для решения исходной задачи.

Распределение модулярных сумм. При рассмотрении разбиения заданного золотого решения (на любом уровне) мы можем построить множество из всех выявляемых левосторонних значений. Для данного множества мы намереваемся изучить распределение скалярного произведения , для заданных значений веса последовательности . Путь обозначает вероятность того, что последовательность из элементов приводит к нахождению значения с по модулю M для одинаково случайно выбранного решения из множества ,

Нашим основным инструментом для теоретического исследования распределения скалярных произведений является следующая теорема [[14], Теорема 3.2]:

TemplateTheoremIcon.svg Теорема Теорема 1
Для любого множества выполняется тождество:

При помощи данного уравнения мы можем доказать нестрогий, но достаточный результат относительно пропорции значений, утраченных при разбиении. Пусть будет произвольным целым числом. Мы намерены установить верхнее ограничение для доли , "неблагоприятных" последовательностей по модулю с числом отысканных значений меньшим, чем . Во-первых, отметим, что для последовательности <math<\ (a_1, ... ,a_n) ~ \, \! </math>, содержащей меньше значений, чем , по меньшей мере значений по модулю отысканы 0 раз. Поскольку

некоторые значения с необходимо отыскивать многократно. В результате выявляем, что

.

Доказательство
Без доказательства.


Это означает, что количество "неблагоприятных" последовательностей соответствует: . При данном предельном значении есть возможность построить вариант нашего алгоритма с доказуемой вероятностью успеха. Учитывая, что есть функция , повторим каждое разбиение для случайных и независимо подобранных значений. Вероятность провала такого повторяемого разбиения равна , за исключением "неблагоприятной" последовательности. Таким образом, общая вероятность отрицательного результата по семи разбиениям меньше, чем 95%. Выбрав меньше (но близкое к нему), мы обеспечиваем то, что общая доля неблагоприятных последовательностей будет максимум равна:

.

Эта часть становится произвольно малой при выборе достаточно большого значения . Обратите внимание, что время работы алгоритма умножается на , поскольку есть три сгруппированных уровня разбиений. Если вероятности успеха 5% недостаточно, есть возможность увеличить эту вероятность посредством повторения всего алгоритма с независимыми произвольными значениями. Алгебраическое число повторений обеспечивает вероятность успеха, экспоненциально приближенное к 1 (за исключением "неблагоприятных" последовательностей).

Анализ размера списков

Относительно размера списков, получаемых во время выполнения алгоритма, простая эвристическая модель, как и результаты экспериментов (см. Раздел 5.1), говорят о том, что размер списков всегда приближен к теоретическим значениям самого низкого уровня, а на более высоких уровнях значения уменьшаются (в силу преувеличения). Остается применить Теорему 1 для установления верхней границы размера разных списков. Для размеров списков мы можем использовать прямое применение теоремы.

Для всех размеров списков можно использовать прямое применение теоремы. Представляющее интерес множество является множеством из всех распределений чисел 1, 0 и -1, что соответствует условиям списка . Модуль является произведением всех активных модулей на текущем и предыдущих уровней. То есть, для уровня мы имеем  ; для уровня , а для уровня берем .

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

.

Используя Теорему 1, устанавливаем:

.

В результате:

.

Ключевой особенностью является то, что последовательность, не являющаяся одной из последовательностей и для большинства значений (за исключением не более, чем ), размер списка меньше, чем умноженное раз ожидаемое значение , то есть,

.

Для ограничения размера списков поступим несколько иначе. Множество состоит из чисел 1, 0 и -1, допущенных в списках и подходящих для построения списка . Записываем , где является произведением активных модулей для списка , а – модуль, прибавляемый при построении списка . Пусть обозначает искомую сумму в качестве нового модулярного ограничения элементов в списке . Пусть и соответственно обозначают значения сумм в левосторонних и правосторонних списках . Разумеется, мы имеем . Можем записать:

.

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

.

Для этого целесообразно переписать соотношение из Теоремы 1 таким образом, чтобы:

.

Учитывая число , мы задаем, что обозначает число последовательностей, для которых значения , превышающие , содержат сумму возведенных в квадрат вероятностей, соответствующих:

.

Устанавливаем, что

 ;

и в результате

.

Более того, при помощи нашего конкретного алгоритма мы можем удостовериться, что всегда выходит, что при формировании списков . Поэтому мы имеем . Для последовательности, не являющейся одной из вышеуказанных последовательностей , а также для большинства значений размер списка меньше, чем умноженное на раз ожидаемое значение то есть:

.

Обратите внимание, что это ограничение включает блок .

Доказуемый вариант конкретного алгоритма

Следуя идеям, представленным в Разделе 3.4, мы можем описать вариант нашего конкретного алгоритма с доказуемым вероятностным временем работы и требуемым пространством. Во-первых, задаем достаточно большое значение . В данном разделе мы повторно определим понятие "неблагоприятной" последовательности утверждением, что последовательность является неблагоприятной, если она не соответствует ни одному из трех критериев, представленных в Разделе 3.4 и Разделе 3.5. То есть, если присутствует слишком много значений, разбиения которых ошибочны или списки типов L или K слишком велики. Определяем, что общая доля неблагоприятных последовательностей меньше, чем

При подборе достаточно большого значения эта доля может стать произвольно малой.

Еще раз рассмотрим вариант конкретного алгоритма, в котором на каждом уровне мы повторяем подбор случайных чисел достаточно часто для достижения успеха. При "благоприятной" последовательности существует три пути, по которым разбиение может дать отрицательный результат. Во-первых, мы можем выбрать случайное значение, не позволяющее осуществить разбиение золотого решения; во-вторых, мы можем выбрать произвольное значение, вызывающее переполнение списка ; в-третьих, мы можем выбрать произвольное значение, вызывающее переполнение списка . Обратите внимание, что последние два действия могут быть выявлены, в случае чего мы стираем списки, сформированные для данного случайного значения и переходим к следующему. Для каждого модуля пропорция случайных значений, являющихся неверными по отношению, по меньшей мере, к одному критерию, - меньше, чем

Поэтому, при кратном повторении каждого разбиения, мы убеждаемся в том, что вероятность отрицательного результата данного разбиения равна максимум . И еще раз, это дает общую вероятность успеха, равную 5%, которая становится экспоненциально приближенной к 1 при алгебраически многократном повторении. С учетом реального соотношения , задавая , получаем следующую теорему:

TemplateTheoremIcon.svg Теорема Теорема 2
Для любого реального соотношения , а также для доли, на которую приходится по меньшей мере уравновешенных последовательностей с плотностью , заданной последовательностью из n-членов и искомым значением , если , является решением последовательности алгоритм, описанный в Разделе 3.3, преобразованный вышеописанным способом, кторый отыскивает решение є, искомое в дальнейшем во времени
Доказательство
Без доказательства.


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

Оптимизация сложности по памяти

В данном разделе мы сначала представим новый алгоритм требуемой постоянной памяти и времени работы алгоритма . Затем покажем способ уменьшения сложности по времени до при помощи метода, аналогичного методу Хаугрэйв-Грэхема и Жу [10] . В завершение мы продемонстрируем компромисс времени и памяти для алгоритма Шроппеля-Шамира до объема памяти.

Алгоритм со временем работы и памятью Алгоритм со временем работы   O ~ ( 2 3 n / 4 )   {\displaystyle \ {\tilde {O}}(2^{3n/4})~\,\!} и памятью   O ~ ( 1 )   {\displaystyle \ {\tilde {O}}(1)~\,\!}

Мы описываем простой алгоритм для решения задачи сверхдлинной последовательности при времени и постоянной памяти, применяя атаку с пересечением в середине. Это производится при формулировании атаки с пересечением в середине как задачи с поиском коллизии (см. [15]); затем можем использовать алгоритм отыскивания цикла постоянной памяти.

Устанавливаем две функции  :

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

.

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

Из двух функций мы устанавливаем функцию , в которой:

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

Однако нам необходимо получить случайную коллизию, тогда как алгоритм Флойда для нахождения цикла всегда ведет к нахождению одной и той же коллизии. Простое решение состоит в дальнейшем внесении элементов случайности в функцию ; более точноЮ алгоритм Флойда для отыскания цикла мы применим для при , где задано как случайное произведение в . Затем новое произведение используем каждый раз, когда для требуется новая коллизия .

Алгоритм со временем работы и необходимой памятью Алгоритм со временем работы O ~ ( 2 0.72 n )   {\displaystyle {\tilde {O}}(2^{0.72n})~\,\!} и необходимой памятью O ~ ( 1 )   {\displaystyle {\tilde {O}}(1)~\,\!}

В данной главе мы покажем, как можно немного уменьшить время работы алгоритма до при остающейся постоянной памяти; для этого используем метод Хаугрэйв-Грэхема-Жу, представленный в Разделе 2.1. И в этот раз для упрощения задания предположим, что кратно , и что вес Хемминга у решения последовательности в точности равен . Как и в (3), переписываем как сумму из двух составляющих последовательности с весом Хемминга , выбранных среди элементов последовательности.

Задаем, что W устанавливается n-последовательностями битов с весом Хемминга . Имеем . Устанавливаем две функции , такие, что:

где обозначает порядковый номер бита значения и аналогично для . Рассматриваем таким образом:

(5)

эквивалентно:

.

Поскольку и являются произвольными функциями, эвристически существует решений для (5). Более того, с учетом правильного решения для последовательности, как показано в Разделе 2.1, существует способов записи этого правильного решения в качестве (см. (3)). Все из этих решений являются решениями для (5). Таким образом, вероятность того, что случайное решение (5) обеспечит верное решение последовательности, равна:

Пространство ввода функций и имеет размер . Таким образом, используя тот же алгоритм нахождения цикла, что и в предыдущем разделе, случайное решение (5) может быть найдено во времени . Следовательно, общая сложность по времени равна:

.

В завершение отметим, что дальнейшая оптимизация этой сложности возможна при добавлении чисел -1 в разбиении (как в Разделе 3), при этом оптимизация временной сложности практически незначительна.

Компромисс времени и памяти при уменьшении памяти до методом Шроппеля-ШамираКомпромисс времени и памяти при уменьшении памяти до 2 n / 16   {\displaystyle 2^{n/16}~\,\!} методом Шроппеля-Шамира

Первоначальный алгоритм Шроппеля-Шамира работает во времени и при памяти . В данном разделе мы опишем постоянный компромисс времени и памяти с уменьшением памяти до . То есть, мы представим вариант алгоритма Шроппеля-Шамира при таких условиях:

Время работы алгоритма: , Память:

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

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

.

Решаем эти четыре уравнения независимо, используя первоначальный алгоритм Шроппеля-Шамира. Таким образом, во времени и при памяти получаем четыре списка , , и , удовлетворяющих четырем уравнениям. В конечном итоге, для нахождения решения последовательности, соединяем эти четыре списка посредством процесса слияния, используемого в первоначальном алгоритме Шроппеля-Шамира; поскольку каждый список имеет размер процесс соединения проходит во времени и при памяти . Поскольку мы предположили три значения, состоящие из битов каждое, суммарное время прохождения задания равно:

как и требовалось, а потребность памяти при этом равна . Не представляет труда произвести обобщение предыдущего алгоритма к памяти для любого решения . Для этого берем значения размером битов каждое. При этом мы можем составить четыре списка во времени при помощи алгоритма Шроппеля-Шамира, но в этот раз размер списков равен , следовательно, требуемая память равна . Процесс слияния сейчас проходит во времени , а требуемая память остается равной . Таким образом, суммарное время работы алгоритма равно:

как и требовалось, а потребность памяти при этом равна .

Рис. 6. Иллюстрация разрыва между нашим алгоритмом с постоянной памятью и нашим компромиссом по времени и памяти Шроппеля-Шамира. 

Как ни удивительно, остается разрыв между нашим вариантом алгоритма Шроппеля-Шамира при памяти и нашим же алгоритмом постоянной памяти из Раздела 4.1. А именно, мы не смогли отыскать вариант алгоритма Шроппеля-Шамира, требующего объема памяти, меньшего, чем , также мы не определили алгоритм на основе цикла, требующего памяти объемом более .

Реализация и экспериментальные доказательства

Реализация алгоритма с улучшенной временной сложностью

Для проверки правильности алгоритма, представленного в Разделе 3.3, мы реализовали его. Реализация была проведена на 50 случайных последовательностях, содержащих 80 элементов на 80 битах. Искомая сумма была образована в каждом случае как сумма из 40 элементов последовательности. Для каждой из этих последовательностей мы провели реализацию по несколько раз, подбирая новые произвольные модулярные ограничения для каждого исполнения до нахождения верного решения. Как показано на рис. 7, мы добавляли два числа -1 на первом уровне, одно число -1 на втором, и не добавляли его на третьем уровне. В то же время, мы составили некоторую статистику о характеристиках поведения нашего кода.

Суммарное время работы алгоритма для решения 50 последовательностей составило 14 часов 50 минут на процессоре Intel Core i7 CPU M 620 при частоте 2.67ГГц. Суммарное время повторений основного алгоритма было равным 280. По нашим наблюдениям, максимального количества 16 повторений (подбор другого произвольного значения на уровне ) было достаточно для нахождения решения. Также для 53% из 50 произвольных последовательностей требовалось лишь до 4 повторений. В среднем, для каждой последовательности требовалось 5.6 повторений.

Таблица 1. Число повторений для 50 случайных последовательностей, пока не найдется решение.

Число повторений Число соответствующих последовательностей Число повторений Число соответствующих последовательностей
1 8 2 6
3 9 4 4
5 2 6 5
7 1 8 1
9 1 10 5
11 4 12 1
13 0 14 1
15 0 16 2

Таблица 2. Экспериментальные и теоретические размеры промежуточных списков.

Тип списка Минимальный размер Максимальный размер Теоретическое значение
12 024 816 12 056 576 12 039 532
61 487 864 61 725 556 61 610 489
12 473 460 20 224 325 31 583 129
14 409 247 23 453 644 57 345 064
183 447 268 964 592 402
178 1 090 21 942

Во время выполнения 280 повторений основного алгоритма мы также измеряли длину списков и (все еще содержащих неподходящие решения) на каждом уровне. Модули подбирались в качестве простых чисел, имеющих размеры, указанные в Разделе 3.3: , и . Экспериментальные и теоретические размеры списков представлены в Таблице 2. В Таблице 2 мы видим, что размеры списков и приближены к прогнозируемым значениям и не имеют значительных отличий. Настоящие размеры списков, тем не менее, меньше, чем предполагаемые. Этот эффект наблюдается от уровня до уровня , делая разрыв между теоретическим значением и все больше. Экспериментальный размер считается из несовместимых решений, соответствующих коллизиям над целыми числами. Вспомним, что наши теоретически установленные верхние границы - коллизии модулей , близкие к .

Рис. 7. Декомпозиция одного решения для сбалансированной последовательности размера 80. Декомпозиция в одинаковые на каждом уровне

Еще несколько тестов. Мы также сделали несколько дополнительных тестов на 240 последовательностях, где мы повторяли каждое решение 10 раз для одной последовательности. Рисунок 8 показывает распределение необходимых повторений, пока не найдется решение. Мы получили и максимум из 41 повторения. В 95% случаев меньше, чем 16 повторений было достаточно, чтобы найти решение. Более того, результаты совпадали со случайными переменными, следующими из распределения предполагаемого значения , где мы предполагали независимость каждой декомпозиции и уровня, и одинаковую возможность успеха . Рисунок также показывает возможность распределения случайных переменных. Ни одна из протестированных случайных последовательностей не была существенно легче или сложнее для решения, чем остальные, за 10 повторений.

Размеры средних списков представлены в Таблице 3. Мы показываем минимальный и максимальный размеры и среднее значение и стандартное отклонение для каждого из списков. Среднее время работы алгоритма на найденное решение - 3.05 минут на повторение и 17.53 минут, чтобы найти решение на процессоре Intel Xeon CPU X5560 2.80ГГц.

Рис. 8. Процент для 240 случайных последовательностей из 10 повторений, на число повторений (Красным); случайная переменная геометрического распределения значений , возможностей , где - среднее время повторений (Зеленым). 

Таблица 3. Экспериментальный размер средних списков дл 240 случайных последовательностей.

Тип списка Минимальный размер Максимальный размер Значение Стандартное отклонение Предполагаемое
12 009 444 12 068 959 12 039 526 3 391 12 039 532
12 231 570 20 233 425 19 924 351 202 256 31 583 129
177 662 269 786 263 337 3 437 592 402

Некоторые результаты для n=96. Мы также протестировали алгоритм для сбалансированных 96-битных последовательностей. Тем не менее, невозможно добавить оптимальное число -1, потому что некоторые списки требуют слишком больших затрат памяти. Вместо этого мы использовали следующее:

  • Разделить последовательность на две подпоследовательности с 25-ю единицами и одной -1.
  • Разделить подпоследовательности с 14 единицами и двумя -1.
  • Наконец, разделить подпоследовательности с 7 единицами и одной -1.

Мы выбрали модули , и . Мы попробовали 5 различных последовательностей и решили все из них за среднее время повторений 7.8. Время работы для одного повторения равно 47 минут на процессоре Intel Xeon X5560 2.80ГГц, при использовании 13 Гб памяти.

Для сравнения, мы также запустили на этой же машине последнюю версию нашей реализации практического варианта алгоритма Хаугрейв-Грэхэма-Жу. Этот вариант использует преимущество 15 минут при решении последовательности из 96 бит, используя 1.6 Гб. Тем не менее, эта программа была более оптимизирована для практических параметров. Более того, она содержит эвристики, чтобы заново использовать много раз вычисления средних списков, чтобы скорость была больше. Следовательно, время работы алгоритма из 96 бит не особо отличаются друг от друга. Мы предполагаем, что пересечение произойдет при n=128, что означает, что 96 бит близко к пересечению между двумя алгоритмами.

Алгоритм с постоянной памятью

Мы также реализовали алгоритм с постоянной памятью, основанный на цикле нахождения из Раздела 4.1. Результаты приведены в Таблице 4 при временной сложности .

Таблица 4. Последовательность длины , число запросов и время работы.

n Минимальный размер Максимальный размер
Время работы
24 21.5 .38с
28 24.4 3.2с
32 26.8 18.0с
36 30.3 226с
40 32.2 933с

Для более детального ознакомления следует обратиться к полной версии нашего отчета [13]; также см. [13] для результатов реализации на 96 битах.

Заключение

Мы дополнили алгоритм Хаугрейв-Грэхема-Жу и получили алгоритм со временем работы . Реализация доступного примера из 80 последовательностей показывает осуществимость метода. У нас есть описанный алгоритм с постоянной памятью, основанный на цикле нахождения со временем и компромиссом времени и памяти по Шроппелю-Шамиру.

Благодарность. Мы хотим поблагодарить Александра Мэя и Александра Мюрера за акцентирование внимания на вопросе противоречивости алгоритма Хаугрэйв-Грэхема-Жу. Также благодарим Дэна Бернштейна за полезные комментарии предыдущей версии этой работы.

Контакты авторов материала

  1. University of Versailles Saint-Quentin-en-Yvelines
  2. University of Luxembourg
  3. University of Versailles Saint-Quentin-en-Yvelines, DGA

Литература

  1. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, 1979.
  2. Ralph C. Merkle and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions On Information Theory, 24:525-530, 1978.
  3. Adi Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In CRYPTO'82, pages 279-288, 1982.
  4. Jerey C. Lagarias and Andrew M. Odlyzko. Solving low-density subset sum problems. J. ACM, 32(1):229- 246, 1985.
  5. Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern. Improved low-density subset sum algorithms. Computational Complexity, 2:111-128, 1992.
  6. Miklos Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In STOC'98, pages 10-19, 1998.
  7. Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomials with rational coecients. Mathematische Annalen, 261:515-534, 1982.
  8. Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci., 53:201-224, 1987.
  9. 9,0 9,1 9,2 Richard Schroeppel and Adi Shamir. A T = O(2n=2); S = O(2n=4) algorithm for certain NP-complete problems. SIAM J. Comput., 10(3):456-464, 1981.
  10. 10,00 10,01 10,02 10,03 10,04 10,05 10,06 10,07 10,08 10,09 10,10 10,11 10,12 10,13 10,14 Nick Howgrave-Graham and Antoine Joux. New generic algorithms for hard knapsacks. In EURO- CRYPT'2010, pages 235-256, 2010.
  11. 11,0 11,1 Alexander May and Alexander Meurer. Personal communication.
  12. David Wagner. A generalized birthday problem. In CRYPTO'2002, pages 288-303, 2002.
  13. 13,0 13,1 13,2 Anja Becker, Jean-Sebastien Coron, and Antoine Joux. Improved generic algorithms for hard knapsacks. Eurocrypt 2011.
  14. Phong Q. Nguyen, Igor E. Shparlinski, and Jacques Stern. Distribution of modular sums and the security of the server aided exponentiation. In Progress in Computer Science and Applied Logic, volume 20 of Final proceedings of Cryptography and Computational Number Theory workshop, Singapore (1999), pages 331-224, 2001.
  15. Paul C. van Oorschot and Michael J. Wiener. Improving implementable meet-in-the-middle attacks by orders of magnitude. In CRYPTO, pages 229-236, 1996.
  16. Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley, 1981.