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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

26
Вычисление символа Лежандра может быть выполнено по следующей
формуле, полученной Леонардом Эйлером:
a
p
= a
p−1
2
mod n. (1.5)
Однако использование этой формулы на практике сопряжено с
вычислениями больших степеней, поэтому предпочтительнее пользоваться
законом квадратичной взаимности, доказанный Карлом Гауссом в возрасте
17 лет.
Закон квадратичной взаимности: для любых нечетных простых
чисел 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
, (1.6)
где n = p
r
1
1
· p
r
2
2
· ... p
r
k
k
–разложение n в произведение степеней простых
чисел.
                                                                           26

         Вычисление символа Лежандра может быть выполнено по следующей
формуле, полученной Леонардом Эйлером:
            
             a     p−1
                = a 2 mod n.                                             (1.5)
             p
         Однако использование этой формулы на практике сопряжено с
вычислениями больших степеней, поэтому предпочтительнее пользоваться
законом квадратичной взаимности, доказанный Карлом Гауссом в возрасте
17 лет.

         Закон квадратичной взаимности: для любых нечетных простых
чисел 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
                 =      ·    · ...       ,                               (1.6)
             n       p1   p1        pk
где n = pr11 · pr22 ·   ... prkk –разложение n в произведение степеней простых
чисел.

Страницы