либо проверить достаточное условие для
Поэтому предлагается:
либо проверить достаточное условие для q=3, что увеличивает скорость вычислений в (3·KMUL) раз при выполнении условия и незначительно (в (1+(1/(3·KMUL))) раз) замедляет скорость вычислений при невыполнении условия;
либо проверить условие для q=3 и для какого-либо простого q, большего трех, что увеличивает скорость вычислений примерно в 3 раза при выполнении условия и замедляет скорость вычислений в 1,33 раза при невыполнении условия.
(KMUL - коэффициент вычислительной трудоемкости операции целочисленного умножения по сравнению с операцией целочисленного сложения для данной аппаратной платформы).
Большее количество проверок с различными значениями q не приносит значимого увеличения средней скорости исчисления критерия. Выбор из предложенных вариантов производится на основе практических значений вероятности PFN и чаще всего обусловлен значением величины (n-k).
Выбор значения q, большего трех, для второго варианта проверки условия производится исходя из следующих соображений. Большие значения q более эффективны в связи с уменьшением вероятности PFN ложного невыполнения достаточного условия. Однако реализация линейных преобразований матрицы R по модулю q задействует предвычисления и хранение таблиц умножения и деления по модулю q, что требует определенных ресурсов вычислительной системы.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий