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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 137
{Making column k equal to 0 below A[k,k]}
while i < mt do
begin
inc(i);
If A[OrdRow[i], k] = 1 Then
begin
For j := 1 To nt do
A[OrdRow[i], j] := (A[OrdRow[i], j] + A[OrdRow[k], j])mod2;
For j := 1 To mt do
E[OrdRow[i], j] := (E[OrdRow[i], j] + E[OrdRow[k], j])mod2;
end;
end;
inc(k);
End; { of cycle by k}
End;
4.8. Вариация множителя в методе квадратичного
решета
Одним из важных улучшений в методе квадратичного решета является
идея вариация большого множителя – Large Prime Variations (LPV). Кратко
эта идея состоит в следующем.
В процессе просеивания накапливается много значений полиномов
q(x), x ∈ [−L; L], которые представимы в виде q(x) = P
x
· C
x
,
где множитель C
x
является гладким числом, а P
x
представляет собой
множитель, превышающий границу гладкости B , но меньший B
2
такой,
что P
x
не содержит делителей из факторной базы. Множитель P
x
является
простым числом, т.к. иначе его можно было бы разложить в произведение
двух сомножителей, меньших B . Назовем все такие значения полугладкими.
Предположим, что мы находимся на этапе, когда первое просеивание,
определяющее номера x гладких чисел, завершено. Выполним цикл
сортировки по всем x ∈ [−L; L], для которых значение остаток значения
y = q(x) после всех делений на числа из факторной базы стал меньше
B
2
, упорядочив все полугладкие числа по возрастанию множителя P
x
.
Предположим, что найдется несколько значений y
1
, y
2
, ..., y
k
, где k ≥ 2,
Глава 4. Метод квадратичного решета                                           137

           {Making column k equal to 0 below A[k,k]}
      while i < mt do
      begin
           inc(i);
           If A[OrdRow[i], k] = 1 Then
           begin
           For j := 1 To nt do
                A[OrdRow[i], j] := (A[OrdRow[i], j] + A[OrdRow[k], j])mod2;
           For j := 1 To mt do
                E[OrdRow[i], j] := (E[OrdRow[i], j] + E[OrdRow[k], j])mod2;
           end;
         end;
         inc(k);
    End; { of cycle by k}
  End;


4.8. Вариация              множителя            в    методе        квадратичного
     решета
     Одним из важных улучшений в методе квадратичного решета является
идея вариация большого множителя – Large Prime Variations (LPV). Кратко
эта идея состоит в следующем.
      В процессе просеивания накапливается много значений полиномов
q(x), x ∈ [−L; L], которые представимы в виде q(x) = Px · Cx ,
где множитель Cx является гладким числом, а Px представляет собой
множитель, превышающий границу гладкости B , но меньший B 2 такой,
что Px не содержит делителей из факторной базы. Множитель Px является
простым числом, т.к. иначе его можно было бы разложить в произведение
двух сомножителей, меньших B . Назовем все такие значения полугладкими.
      Предположим, что мы находимся на этапе, когда первое просеивание,
определяющее номера x гладких чисел, завершено. Выполним цикл
сортировки по всем x ∈ [−L; L], для которых значение остаток значения
y = q(x) после всех делений на числа из факторной базы стал меньше
B 2 , упорядочив все полугладкие числа по возрастанию множителя Px .
Предположим, что найдется несколько значений y1 , y2 , ..., yk , где k ≥ 2,

Страницы