Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод квадратичного решета.

Читайте также:
  1. Battement tendu. Методика преподавания, виды.
  2. I. Задачи и методы психологии народов.
  3. II. Метод они должны иметь поистине универсальный, где нужно соблюдать следующее.
  4. III. Методы строительства
  5. IV. Изучите методику объективного обследования.
  6. IV. Методические указания студентам по подготовке к занятию
  7. PEST-аналіз як ефективний метод дослідження макросередовища діяльності підприємства.

Пусть n – число, которое надо факторизовать. Как и метод Ферма, данный метод ищет целые числа x, y: n=x 2 —y 2, но подход к поиску несколько иной. Поиск числа x осуществляется не среди всех чисел подходящего размера. Перед началом перебора производится отсев некоторых чисел.

Принцип отсева вытекает из следующих рассуждений: Возьмем небольшое число m и рассмотрим полную систему вычетов Z m ={0, 1, 2, …, m —1}. Среди чисел из Z m некоторые числа являются квадратами (то есть квадратичными вычетами), а другие не являются. Если m – простое число, то квадратов столько же, сколько неквадратов. Если m – составное, то квадратов несколько меньше. В общем случае,

P(s Q(m)) ≤ .

Если число не является квадратичным вычетом по какому-то модулю m, то оно не является квадратом в Z, поэтому число y 2 следует искать среди тех чисел, которые являются квадратами в Z m.

В методе квадратичного решета берут несколько небольших попарно простых модулей m 1, m 2, …, mk. Для каждого такого модуля составляют квадратичное решето (двоичный вектор S m) следующим образом:

Для каждого x Z m вычисляют x 2 mod m и z =(x 2 —n) mod m. Если z является квадратом по модулю m, то S m (x)=1, иначе S m (x)=0. Проверка того, является ли z квадратом по модулю m, производится путем сверки с вычисленными x 2 mod m.

X       m –1
x2 mod m     22 mod m (m –1) 2 mod m
z = x2n mod m     z 2 zm —1

 

После того, как все решёта построены, начинается отсев кандидатов x. Решёта накладываются на последовательность чисел x от +1 до . Те числа, на которые наложился «0» хотя бы одного решета, отсеиваются. После отсева остается достаточно небольшое количество чисел – кандидатов в x. Для каждого такого числа вычисляется x 2, z= x2n и y= . Если y 2 =z, то числа a=x+y, b=x—y являются делителями числа n.

Пример:

n =279.

Построим решёта по модулям 4, 5 и 7:

x        
x2 mod 4        
Z = x2 –279 mod 4        
S4        

 

x          
x2 mod 5          
z = x2 –279 mod 5          
S5          

 

x              
x2 mod 7              
z = x2 –279 mod 7              
S7              

 

Теперь, когда мы построили три решета, наложим их на последовательность чисел от +1=17 до =140.

Поскольку 17 mod 4 = 1, то наложение решета S4 начнем с S4(1),

17 mod 5 = 2, то наложение решета S5 начнем с S5(2),

17 mod 7 = 3, то наложение решета S7 начнем с S7(3).

x                                    
S4                                    
S5                                    
S7                                    

 

Среди чисел от 17 до 34 остались 20, 22, 28,

Проверим их:

x =20, x 2=400, z=x 2 —n =121, y = =11, y 2=121= z.

Тогда a=x+y =31, b=x—y =9.

Ответ: 279=31·9.

 


Дата добавления: 2015-09-07; просмотров: 264 | Нарушение авторских прав


Читайте в этой же книге: Теорема 1. | Символ Лежандра. | Тест на простоту Соловея-Штрассена. | Квадраты и псевдоквадраты. | Числа Блюма. | Криптосистема Блюма-Гольдвассер (Blum-Goldwasser). | Криптосистема Гольдвассер-Микали. | Тест на простоту Миллера-Рабина. | Теорема Сэлфриджа. | Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1). |
<== предыдущая страница | следующая страница ==>
Теорема Диемитко.| Травмы груди

mybiblioteka.su - 2015-2024 год. (0.006 сек.)