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

Глава 1. Системы шифрования с открытым ключом                                28

от 3 до B . Затем выбираем первое число в списке, т.е. тройку, и оставляя
его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко
второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму
пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут
только простые числа.
      Следующая теорема дает критерий проверки простоты числа p и
одновременно примитивности корня a:

Теорема 2.3. (Критерий        примитивности         и   простоты).   Если   для
некоторых a и p выполнены условия:

   1. ap−1 ≡ 1( mod p),
   2. a(p−1)/q ̸≡ 1( mod p) для ∀q|(p − 1),

тогда число p–простое, и a является примитивным корнем поля GFp (т.е.
генератором группы по умножению поля GFp ).

Пример. n = 1 022 333 835 329 657, n − 1 = 2 · 2957 · 146 063 · 292 877.

       3n−1 ≡ 1( mod n),
       3(n−1)/2 ≡ −1 ( mod n),
       3(n−1)/2597 ≡ 324224767363906 ( mod n),
       3(n−1)/146 063 ≡ 697302646321792 ( mod n),
       3(n−1)/292 877 ≡ 736785752408036 ( mod n).

      Поэтому число n в нашем примере является простым, а 3 является
примитивным корнем поля Галуа GFn .
      Отметим, что разбиение n − 1 в произведение простых сомножителей
само является очень сложной задачей, поэтому для длинных чисел этот
критерий простоты неприменим.


2.8. Метод пробных делений
      Метод пробных делений (the trial division) является наиболее простым
методом проверки простоты входного составного числа n или нахождения
его делителей. Будем использовать обозначение ⌊x⌋ для функции floor(x),