Теория и практика защиты программ


         

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


Сначала, мы покажем, как выбирать и сохранять в ЦП

случайную перестановку над {1,2,...,n}, используя O(logn) памяти и случайный оракул. Идея состоит в том, чтобы использовать оракул для проставления меток случайно выбранных элементов и различные целые числа из множества меток, обозначаемого Tn. Перестановка получается посредством сортировки элементов в соответствии с их метками. Если же необходимо получить вероятность коллизии e

(т.е., для нашего приложения e=2-2k), достаточно иметь метки, выбранные случайно из множества Tn={1,2,...,n2/e},. Пусть t : {1,2,...,n}®Tn - случайная функция, тривиально созданная случайным оракулом. В этом случае p(i)=k, тогда и только тогда, когда p(i) - наименьший элемент в {t(j):1£j£n}. В нашем случае n=m+

, а именно n элементов состоят из m виртуальных адресов, связанных с целыми числами 1,...,m

и

 макетов, связанных с (m+1,...,

m+

}.

Теперь мы имеем дело с задачей забывающей сортировки n

элементов посредством меток. Определяющее условие состоит в том, что

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



Содержание  Назад  Вперед