Реализация алгоритма "Квадратного корня

Реализация алгоритма "Квадратного корня"

Сначала, мы покажем, как выбирать и сохранять в ЦП случайную перестановку над {1,2,...,n}, используя O(log n) памяти и случайный оракул. Идея состоит в том, чтобы использовать оракул для проставления меток случайно выбранных элементов и различные целые числа из множества меток, обозначаемого Tn. Перестановка получается посредством сортировки элементов в соответствии с их метками. Если же необходимо получить вероятность коллизии ε (т.е., для нашего приложения ε=22k), достаточно иметь метки, выбранные случайно из множества Tn={1,2,...,n2/ε},. Пусть τ: {1,2,...,n} > Tn случайная функция, тривиально созданная случайным оракулом. В этом случае π(i)=k, тогда и только тогда, когда π (i) наименьший элемент в {τ(j):1jn}. В нашем случае n=m+, а именно n элементов состоят из m виртуальных адресов, связанных с целыми числами 1,...,m и макетов, связанных с (m+1,..., m+}.

Теперь мы имеем дело с задачей забывающей сортировки n элементов посредством меток. Определяющее условие состоит в том, что RAMмашина, которая выполняет сортировку, может хранить только фиксированное число значений одновременно. Идея состоит в том, чтобы "выполнить" сортирующую сеть Батчера, который позволяет сортировать n элементов, выполняя n|log2n| 2 сравнений. Каждое сравнение "выполняется" посредством осуществления доступа к двум соответствующим словам, чтением их содержания и записью этих значений обратно в необходимом порядке. Последовательность операций доступа к памяти, сгенерированной для этой цели фиксирована и не зависит от входа. Отметим, что забывающая RAMмашина может легко вычислять в каждой точке, какое сравнение требуется для реализации следующего. Это следует из простой структуры сети Батчера, которая является однородной относительно логарифмического пространства. Этот алгоритм будет работать, если мы сохраняем метку каждого элемента вместе с самим элементом (виртуальное слово или макет).

Далее мы точно определим, как осуществить доступ к виртуальной ячейке или к макету i. Отметим, что после шага 1 виртуальные ячейки от 1 до m (также как и макеты от m+1 до m+) сортируются согласно их меток (т.е., τ(')). Таким образом, фактический доступ в перемешанную память на шаге 2 выполняется двоичным поиском необходимой метки. А именно, предположим, что мы хотим получить доступ к элементу i {1,...,m+}. Затем, вместо того, чтобы непосредственно достичь фактической ячейки π(i), как предлагается выше, мы выполняем двоичный поиск метки π(i). Этот двоичный поиск заканчивается на фактической ячейке π(i). Помимо этого другие фактические операции доступа, выполняемые во время поиска, полностью определены π(i). Таким образом, эти дополнительные фактические операции доступа не открывают никакой информации наблюдателю (противнику).

Далее описываются две альтернативных реализации шага 3. Первый вариант реверсия модели доступа на шаге 2. Второй вариант полная сортировка фактической памяти (то есть, все m+2 слов, включая память зщт) дважды как описано в алгоритме. Первая сортировка выполняется в соответствии с ключом (v,σ ), где v виртуальный адрес ( для макетов) и σ {0,1} указывает, исходит ли это слово из памяти зщт или из перемешанной памяти. Таким образом, сортируемый список имеет виртуальные адреса, появляющиеся так, чтобы некоторые из них появляются в двойном экземпляре, один за другим (одна версия из памяти зщт, а другая из перемешанной памяти). Затем, мы сканируем этот список и для каждого виртуального адреса, появляющегося в дубликате, маркируется второе местонахождение (возникающее из перемешанной памяти) также как и макет (т.е.). В заключение, мы снова полностью сортируем память, но на сей раз виртуальными адресами. Фактически, эта дополнительная сортировка не нужна, поскольку память будет подвергнута пересортировке когдалибо при следующем выполнении шага 1.

Далее следует детальное описание шага 2. Главная идея при этом моделировании состоит в том, чтобы осуществить доступ к каждой виртуальной ячейке в "перемешанной памяти" только в течение каждого шага периода. Как только "осуществиться" доступ к некоторой виртуальной ячейке, необходимо сохранить версию этой виртуальной ячейке в памяти зщт. В течение шага 2, счт содержит число виртуальных операций доступа, моделируемых в текущем периоде. Переменная счт первоначально содержит 0 и увеличивается, пока достигнет значения. Булева переменная found будет инициироваться, если требуемое значение найдено в памяти зщт. Когда оригинальная RAMмашина осуществляет доступ к iтому виртуальному слову, забывающая RAMмашина работает следующим образом:

  • (2a) сканирует полностью память зщт и ищет виртуальный адрес i. А именно, для j, пробегающему значения от m+ +1 до m+2, доступ к фактической ячейке памяти j переменная found устанавливается в true и сохраняется в ЦП, если виртуальный адрес i совпадает с фактической ячейкой j. (Переменная found инициализирована в значение false до этого сканирования и остается такой же, если виртуальный адрес i не был найден);
  • (2b) если found=false, тогда забывающая RAMмашина осуществляет доступ к слову с меткой π(i) и сохраняет содержимое в ЦП. Как показано выше, это реализуется посредство двоичного поиска метки π(i);
  • (2c) если found=true, тогда забывающая RAMмашина осуществляет доступ к слову с меткой π(m+счт), которое является "макетом". Это также реализуется посредством двоичного поиска метки π(m+счт);
  • (2d) просматривает полностью память зщт снова и записывает модифицируемое значение iтого виртуального слова в памяти зщт. А именно, для m+ +1 до m+2 доступ к фактической ячейке памяти j запоминается в ее модифицированном значении виртуального адреса i, если адрес j содержит старое значение виртуального адреса i (т.е., found=true), либо found=false и j первое пустое слово в shelterе.
  • Значение счт увеличивается на 1.

Подчеркнем, что наблюдатель не может видеть, сохранил ли ЦП значения или нет и, таким образом, не может различать выполнение шага 2b от выполнения шага 2c. Ясно, что шаги 2a и 2d имеют фиксированную модель доступа и, таким образом, не никакая информация, полезная для наблюдателя, не вскрывается.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок