Математические основы защиты информации. Ишмухаметов Ш.Т - 33 стр.

                                                                        34

выяснится, что n–составное число, то выберем новое значение R и повторим
вычисления.

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


2.12. Символ Лежандра
Определение 2.3. Пусть n > 1–целое число. Число a, принадлежащее
интервалу [0, n − 1] называется квадратичным вычетом по модулю n, если
найдется целое число x такое, что x2 ≡ a ( mod n).

      Если такого x не существует, то a называется квадратичным
невычетом. Отметим, что ровно половина элементов из интервала [0, n − 1]
является квадратичными вычетами.
      Условия того, является ли a квадратичным вычетом по простому
модулю p, проверяется с помощью, так называемого, символа Лежандра:
                
        ( )    
                   1, если (∃ x) x2 ≡ a mod p,
          a
             =    −1, если не(∃ x) x2 ≡ a mod p,                 (2.7)
          p     
                
                 0, если p | a.

      Вычисление символа Лежандра может быть выполнено по следующей
формуле, полученной Леонардом Эйлером:
           ( )
             a     p−1
                = a 2 mod n.                                          (2.8)
             p

      Однако использование этой формулы на практике сопряжено с
вычислениями больших степеней, поэтому предпочтительнее пользоваться
законом квадратичной взаимности, доказанный Карлом Гауссом в возрасте
17 лет.