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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 77
Метод получения редуцированной формы, эквивалентной данной, был
найден еще Карлом Гауссом и состоит в последовательном применении
оператора редукции f = ρ(f), пока f не станет редуцированной:
Определение. Оператор редукции ρ(f)– это оператор на классе
квадратичных бинарных форм с целыми коэффициентами, который
определяется следующим образом:
ρ(f) = ρ(a, b, c) =
c, r,
r
2
− D
4c
,
(2.50)
где r = r(−b, c)–целое число, однозначно определяемое следующими
условиями:
1. r ≡ −b ( mod 2c),
2. −|c| < r ≤ |c|, если
√
D < |c|,
3.
√
D −2|c| < r <
√
D, если |c| <
√
D.
Результат применения оператора ρ к форме f n раз записывается
ρ
n
(f). Обратный к ρ оператор ρ
−1
определяется следующим образом:
ρ
−1
(a, b, c) =
r
2
− D
4a
, r, a
,
(2.51)
где r = r(−b, c) определено как и раньше. Справедлива следующую теорему:
Теорема 2.4. Каждая форма f эквивалентна некоторой редуцированной
форме, и любая редуцированная форма для f равна ρ
k
(f) для некоторого
положительного k. Если f –редуцирована, то ρ(f) также редуцирована.
Определение. Две формы (a, b, c) и (c, b
0
, c
0
) называются
смежными (adjacent), если выполняется условие b + b
0
≡ 0 (mod 2c ).
Каждая форма (a, b, c) эквивалентна некоторой смежной форме, а именно,
(a, b, c) ∼ (c, −b, a) (2.52)
Также на множестве эквивалентных форм можно определить
операцию умножения (композицию), тогда, если коэффициенты a и b
Глава 2. Простые алгоритмы факторизации                                           77

Метод получения редуцированной формы, эквивалентной данной, был
найден еще Карлом Гауссом и состоит в последовательном применении
оператора редукции f = ρ(f ), пока f не станет редуцированной:
        Определение. Оператор редукции ρ(f )– это оператор на классе
квадратичных бинарных форм с целыми коэффициентами, который
определяется следующим образом:
                             r2 − D
                                   
  ρ(f ) = ρ(a, b, c) = c, r,          ,
                                4c
                                                                               (2.50)
где r    = r(−b, c)–целое число, однозначно определяемое следующими
условиями:

  1. r ≡ −b ( mod 2c),
                         √
  2. −|c| < r ≤ |c|, если D < |c|,
     √                 √           √
  3. D − 2|c| < r < D , если |c| < D .

        Результат применения оператора ρ к форме f n раз записывается
ρn (f ). Обратный к ρ оператор ρ−1 определяется следующим образом:
                  2            
                  r  −  D
 ρ−1 (a, b, c) =          , r, a ,
                     4a
                                                                               (2.51)
где r = r(−b, c) определено как и раньше. Справедлива следующую теорему:

Теорема 2.4. Каждая форма f эквивалентна некоторой редуцированной
форме, и любая редуцированная форма для f равна ρk (f ) для некоторого
положительного k . Если f –редуцирована, то ρ(f ) также редуцирована.

        Определение.      Две    формы    (a, b, c)   и   (c, b0 , c0 )   называются
смежными (adjacent), если выполняется условие b + b0 ≡ 0 (mod 2c ).
Каждая форма (a, b, c) эквивалентна некоторой смежной форме, а именно,

        (a, b, c) ∼ (c, −b, a)                                                 (2.52)

        Также на множестве эквивалентных форм можно определить
операцию умножения (композицию), тогда, если коэффициенты a и b

Страницы