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

                                                                               25

      Случай 2. B ≥ A/2. Остаток r = A mod B = A − B будет меньше
A/2, и на шаге k + 2 новое значение A станет равным остатку r < A/2.

      В любом случае, после каждой пары итераций первый аргумент A
уменьшается более, чем в 2 раза, значит, общее число итераций не может
быть больше, чем 2 log2 A. Число операций на каждой итерации постоянно
(как при прямом ходе, так и при подъеме при вычислении коэффициентов
уравнения Ax+By = d), поэтому, оценка РАЕ равна O(L), где L = dlog2 Ae–
длина двоичного представления меньшего из чисел.
      Эта     оценка     не    является      завышенной,      т.к.    существует
последовательность чисел Фибоначчи, {Fn }, на парах соседних элементов
которых и достигается эта верхняя оценка. Последовательность или ряд
Фибоначчи определяется следующими формулами:

      F0 = 1, F1 = 1, Fn+2 = Fn + Fn+1 , n ≥ 2.

Выпишем начальный интервал этого ряда:

S = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181}.


1.9. Символ Лежандра
Определение 1.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,                 (1.4)
          p     
                 0, если p | a.
                