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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 141
Если значения a, b, c выбраны, то этап инициализации заключается
в решении уравнения
ax
2
+ 2bx + c ≡ 0 ( modp) (4.118)
для каждого простого p < B , где B –граница факторной базы, для которого
уравнение
t
2
≡ n( modp) (4.119)
имеет решение. Если уравнение (4.119) разрешимо, то обозначим через t
p
его
корень (любой из двух возможных). Тогда решения уравнения (4.118) можно
записать в виде
r
1
= (−b + t
p
)a
−1
( mod p), r
2
= (−b − t
p
)a
−1
( mod p). (4.120)
Таким образом, основная работа на этапе инициализации состоит в
вычислении a
−1
( mod p) для каждого простого числа p ∈ F B .
Зададим полином z
a,b
(x) = a(ax
2
+ 2bx + c), в котором a является
произведением нескольких простых чисел из факторной базы. Полином
z
a,b
(x) будет гладким тогда и только тогда, когда гладким будет значение
выражения ax
2
+ 2bx + c. Кроме того для каждого значения a можно
найти несколько соответствующих ему значений коэффициента b. Пусть a =
q
1
· q
2
·, ... q
s
, q
i
∈ F B . Для того чтобы сгенерировать полином нужно найти
b, b
2
≡ n (mod a). Существует 2
s
значений b (moda), удовлетворяющих
этому условию. Но только половина из них может быть использована, так как
z
a,b
(x) дает те же значения вычетов, что и z
a,−b
(x). Таким образом можно
найти 2
s−1
полиномов при неизменном значении коэффициента a.
Нужно найти целые числа B
i
, 1 ≤ i ≤ s, удовлетворяющие условиям:
B
2
i
≡ n (mod q
i
), B
i
≡ 0 (mod a/q
i
) (4.121)
тогда по китайской теореме об остатках любое значение b можно записать в
виде
b = ±B
1
± B
2
... ± B
s
( mod a), (4.122)
Глава 4. Метод квадратичного решета                                        141

        Если значения a, b, c выбраны, то этап инициализации заключается
в решении уравнения

          ax2 + 2bx + c ≡ 0 ( modp)                                     (4.118)

для каждого простого p < B , где B –граница факторной базы, для которого
уравнение
                    t2 ≡ n( modp)                                       (4.119)

имеет решение. Если уравнение (4.119) разрешимо, то обозначим через tp его
корень (любой из двух возможных). Тогда решения уравнения (4.118) можно
записать в виде

          r1 = (−b + tp )a−1 ( mod p), r2 = (−b − tp )a−1 ( mod p).     (4.120)

Таким образом, основная работа на этапе инициализации состоит в
вычислении a−1 ( mod p) для каждого простого числа p ∈ F B .
        Зададим полином za,b (x) = a(ax2 + 2bx + c), в котором a является
произведением нескольких простых чисел из факторной базы. Полином
za,b (x) будет гладким тогда и только тогда, когда гладким будет значение
выражения ax2 + 2bx + c. Кроме того для каждого значения a можно
найти несколько соответствующих ему значений коэффициента b. Пусть a =
q1 · q2 ·, ... qs , qi ∈ F B . Для того чтобы сгенерировать полином нужно найти
b, b2 ≡ n (mod a). Существует 2s значений b (moda), удовлетворяющих
этому условию. Но только половина из них может быть использована, так как
za,b (x) дает те же значения вычетов, что и za,−b (x). Таким образом можно
найти 2s−1 полиномов при неизменном значении коэффициента a.
        Нужно найти целые числа Bi , 1 ≤ i ≤ s, удовлетворяющие условиям:

    Bi2 ≡ n (mod qi ),    Bi ≡ 0 (mod a/qi )                            (4.121)

тогда по китайской теореме об остатках любое значение b можно записать в
виде

       b = ±B1 ± B2 ... ± Bs ( mod a),                                  (4.122)

Страницы