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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

35
Закон квадратичной взаимности: для любых нечетных простых
чисел p и q выполняется формула
(
q
p
)
=
(
p
q
)
(−1)
(p−1)(q−1)/4
.
Иначе говоря,
(
q
p
)
= −
(
p
q
)
, если p ≡ q ≡ 3 mod 4, и
(
q
p
)
=
(
p
q
)
, иначе.
Гаусс в течение своей жизни неоднократно возвращался к этому
закону и получил несколько его доказательств, основанных на совершенно
различных идеях.
Для быстрого вычисления символа Лежандра полезными являются
также следующие формулы:
(
q
p
)
=
(
q mod p
p
)
,
(
q · r
p
)
=
(
q
p
)
·
(
r
p
)
,
(
2
p
)
= (−1)
p
2
−1
8
mod n.
Пример. Вычислить (15/17):
(
15
17
)
=
(
3
17
)
·
(
5
17
)
=
(
2
3
)
·
(
2
5
)
= (−1) · (−1)
3
= 1
Для составных чисел n используется символ Якоби, который является
обобщением символа Лежандра на произвольные целые числа и обладает
следующим свойством:
(
a
n
)
=
(
a
p
1
)
r
1
·
(
a
p
1
)
r
2
· ...
(
a
p
k
)
r
k
, (2.9)
где n = p
r
1
1
· p
r
2
2
· ... p
r
k
k
–разложение n в произведение степеней простых
чисел.
2.13. Тест простоты Миллера–Рабина
В качестве критерия проверки, является ли заданное число n простым
или составным, может служить следующая теорема:
                                                                           35

         Закон квадратичной взаимности: для любых нечетных простых
чисел p и q выполняется формула
               ( ) ( )
                q      p
                   =     (−1)(p−1)(q−1)/4 .
                p      q
     Иначе говоря,
  ( )    ( )                            ( ) ( )
   q       p                             q   p
      =−      , если p ≡ q ≡ 3 mod 4, и    =    , иначе.
   p       q                             p   q
         Гаусс в течение своей жизни неоднократно возвращался к этому
закону и получил несколько его доказательств, основанных на совершенно
различных идеях.
         Для быстрого вычисления символа Лежандра полезными являются
также следующие формулы:
 ( ) (           )   (     ) ( ) ( )                 ( )
  q      q mod p       q·r    q   r                   2        p2 −1
     =             ,        =   ·    ,                   = (−1) 8 mod n.
  p         p           p     p   p                   p

    Пример. Вычислить (15/17):
( ) ( ) ( ) ( ) ( )
 15    3     5     2     2
    =    ·      =      ·    = (−1) · (−1)3 = 1
 17   17    17     3     5
         Для составных чисел n используется символ Якоби, который является
обобщением символа Лежандра на произвольные целые числа и обладает
следующим свойством:
            ( ) ( )r1 ( )r2        ( )rk
             a       a    a         a
                 =      ·    · ...       ,                               (2.9)
             n       p1   p1        pk

где n = pr11 · pr22 ·   ... prkk –разложение n в произведение степеней простых
чисел.


2.13. Тест простоты Миллера–Рабина
      В качестве критерия проверки, является ли заданное число n простым
или составным, может служить следующая теорема:

Страницы