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


Алгоритм A*B modulo N - алгоритм выполнения операции модулярного умножения - часть 4


принимает максимально возможное значение Pi-1=N-1, а N, A и B[i] заведомо тоже велики: N=rn+1-1, A=rn+1-2, B[i]=r-1. Тогда на i-том шаге согласно (2.1.8):

 

Pi'=(rn+1-2)*r+(rn+1-2)*(r-1)=2*rn+2-rn+1-4*r+2                  (2.1.16)

                             (2.1.17)

 

При достаточно большом m, если не введена проверка (2.1.6), то k<2*r-1, по условию же 0<k<r-1. И из (2.1.16) и (2.1.17) видно, что P

придется представлять m+2 разрядами (что определяется слагаемым 2*rn+2), по условию же m+1. Если же ввести проверку (2.1.7), то даже при d=0,5 т.е.

Pi-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то Pi

меняет знак на противоположный (сравн. (2.1.11), (2.1.12), (2.1.14) и (2.1.15)), из (2.1.6) и (2.1.7) получим, что 0£k<(1/2)*r-1, что удовлетворяет наложенному на k

условию, и для представление P

достаточно m+1 разряда.

В алгоритме P

используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D

в работе [Кн, стр.291-295]). Чем больше основание системы счисления r, тем меньше вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.

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

 

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

 




- Начало -  - Назад -  - Вперед -