51418

Факторизация больших чисел

Доклад

Математика и математический анализ

2 Пусть S множество содержащее r элементов функция выбранная случайным образом из конечного числа функций.4 Существует взаимнооднозначное соответствие между представлением числа n в виде и в виде а именно: ; . Тогда мы будем подбирать такие числа t и s чтобы было квадратом небольшого числа s. Если полученные таким образом числа и не делят n то берется или .

Русский

2014-02-11

386.5 KB

16 чел.

Раздел VІII

Факторизация больших чисел

Проблема факторизации заключается в разложении чисел на простые множители.

  1.  Метод Монте-Карло (Полларда, r-метод)

Пусть nнекоторое число, и задано отображение ZZn (Znкольцо вычетов по модулю n). Построим следующее множество элементов :

Znпроизвольное,

,

Утверждение 8.1 (Метод Монте-Карло) Если для некоторых j и k ()  таковы, что , где , то  является делителем n.

Пример. .

Пусть . Полагаем

,

, , , … и т.д.

, ,  .

Утверждение 8.2 Пусть Sмножество, содержащее r элементов,  – функция, выбранная случайным образом из конечного числа функций. Тогда если множество X содержит  элементов, где lположительное действительное число, то вероятность того, что все элементы множества X различны, не превосходит .

Утверждение 8.3 Оценка трудоемкости метода Монте-Карло Если nнечетное составное число, нетривиальный делитель n, то трудоемкость метода составляет .

Модификация метода. Пусть k (количество элементов множества X) имеет  двоичных разрядов. Тогда рассматриваются разности , где  (т.е. j имеет h двоичных разрядов).

Пример. При k, равном 10, оно имеет 4 двоичных разряда, тогда j имеет 3 двоичных разряда, и по модификации равно 7.

  1.  Метод Ферма и его простейшие модификации

Предположим, что составное число n представимо в виде произведения простых чисел , . Задача состоит в нахождении этих простых чисел.

Утверждение 8.4 Существует взаимно-однозначное соответствие между представлением числа n в виде  и в виде , а именно:

,  ;

,  .

Из утв. 8.4 следует, что если a и b близки, то s – небольшое. Тогда мы будем подбирать такие числа t и s, чтобы  было квадратом небольшого числа s. В этом случае удобно взять или близкое к нему.

Примеры.

  1.  

.

– не является квадратом.

Возьмем : , т.е. .

Итак, , .

Проверка: .

  1.  . Если действовать так, как было показано в примере 1, то мы достигнем успеха только на 38-м шаге, поэтому стоит рассмотреть модификации данного метода.

Модификация метода 1. Если не удается быстро подобрать t, то можно рассматривать , где N, или близкие к нему. Тогда . Если полученные таким образом числа  и  не делят n, то берется  или .

Пример. .

Рассмотрим :  – не является квадратом. Возьмем : , т.е. . . Таким образом .

Модификация метода 2. Рассмотрим сравнение , вытекающее из представления n в виде разности квадратов. Его можно переписать в виде . Можно подбирать числа t и s в соответствии с этим сравнением.

Пример.

Рассмотрим : , , т.е. , . . . Таким образом, .

  1.  Метод фактор-базы и его модификации

Вторая простейшая модификация метода Ферма поставила новую проблему: как подобрать числа t и s, заведомо удовлетворяющие сравнению ? Метод фактор-базы решает эту проблему.

Из простых чисел формируется множество  (база), где , а остальные числа – все различные и небольшие. Предположим, что имеется набор чисел  таких, что . Утверждается, что этот набор и будет содержать подходящие для t и s числа.

Пример. .

Выберем базу . Рассмотрим число :

,

т.е. число b можно выбрать в качестве t.

Другие подходящие числа:

,

.

Модификация метода 1. Пусть база . Рассмотрим h-мерное линейное векторное пространство над F2: каждому числу из набора  поставим в соответствие вектор . Если векторы  такие, что , то  можно представить в виде , где степени  – четные. Обозначим . Имеем:

,

причем  – четное. Обозначим , . Используя это, получаем соотношение , где , откуда вытекает условие нетривиальности:

.

Если это условие выполняется, то b считается подходящим и может быть выбрано в качестве t, а cв качестве s.

Пример. , .

,  

Таблица степеней для разложений :

.

.

Результат: .

Оценка трудоемкости метода фактор-базы составляет , где . В хороших алгоритмах .

Модификация метода 2. Основана на том, что если  – небольшое, то x с большей вероятностью раскладывается в произведение простых чисел. Используя это, в качестве  можно выбирать числа , , N или близкие к ним.

Пример. , .

,

,

,

Аналогично набираются остальные bi, представленные ниже в таблице:

bi

Степени элементов базы в разложении

42

1

0

0

1

0

0

1

43

0

2

0

1

0

0

0

61

0

0

2

0

1

0

0

74

1

0

0

0

0

1

0

85

1

0

0

0

1

0

1

86

0

4

0

1

0

0

0

, ,  ,

т.е. данное b не подходит. Рассмотрим другой вариант.

,  ,  ,

.

В итоге .

Модификация метода 3. В предыдущих модификациях числа из набора  выбирались в основном случайным образом. Данная модификация метода фактор-базы предназначена для поиска таких чисел.

Из теории чисел изветсно, что любое число x раскладывается в непрерывную дробь:

  

  

и т.д.

Такое разложение конечно тогда и только тогда, когда xрациональное число.

Если ввести обозначения , ; , , то дроби вида , где , ,  назыв. подходящими дробями разложения числа x в непрерывную дробь.

Утверждение 8.5 Если  – подходящая дробь, то .

Утверждение 8.6 Если  – подходящие дроби, то : .

Теперь рассмотрим применение этих результатов. Имеется набор чисел  таких, что  разлагается в произведение степеней элементов базы B. Разложим  в непрерывную дробь (скорей всего, она будет бесконечной). По утв. 8.6 имеем:

.

Теперь предположим, что  и будем искать :

,

откуда получаем оценку:

.

  1.  Алгоритм факторизации числа с помощью непрерывных дробей
  2.  Полагаем: , , , .
  3.  Вычисляем .
  4.  Полагаем для  , , .
  5.  Вычисляем (наименьший по абсолютной величине вычет).

Пример.

i

0

1

2

3

4

qi

95

3

1

26

2

i

0

1

2

3

4

bi

95

286

381

1119

2619

i

0

1

2

3

4

-48

139

-7

87

-27

Выбираем базу .

не раскладывается в выбранной базе

не раскладывается в выбранной базе

Рассмотрим сумму .

  1.  

18


 

А также другие работы, которые могут Вас заинтересовать

66559. Построение беспроводной системы видеонаблюдения 40.5 KB
  Оборудование: Беспроводные адаптеры (типа DWL-G132) – по одному на пользователя Точки доступа (типа DWL-2100AP) – 1 штука Видеокамеры (типа DCS-2100G) – 3 штуки Цель работы: Изучение основ построения систем видеонаблюдения. Создание беспроводной системы видеонаблюдения в локальной сети...
66560. Исследование операционных усилителей 38.35 KB
  Цель работы. Исследование свойств и характеристик операционных усилителей в качестве масштабного преобразователя, интегратора, дифференцирующего элемента. Принципиальная схема операционного усилителя KIУТ40IБ.
66561. ДОСЛІДЖЕННЯ ТРИФАЗНОГО ЕЛЕКТРИЧНОГО КОЛА ПРИ 3’ЄДНАННІ СПОЖИВАЧІВ ТРИКУТНИКОМ 877.5 KB
  Дослідити трифазне електричне коло при з’єднанні фаз споживачів трикутником при різних режимах роботи та різних навантаженнях. Перевірити основні співвідношення між лінійними і фазними напругами та струмами.
66565. Налаштування конфігурації системи в CMOS-Setup 173 KB
  Мета: Вивчити основні принципи роботи BIOS та призначення розділів і пунктів CMOS-Setup. Навчитися налаштовувати параметри CMOS-Setup на максимальну продуктивність. Перед завантаженням операційної системи в комп'ютері починає виконання вбудована в чіп материнської плати програма BIOS (Base Input/Output System, основна система вводу-виводу).
66566. Освоєння технології структурного та модульного програмування при розробці й створенні програми мовою Турбо Паскаль при реалізації на ПЕОМ задач з використанням функцій 137 KB
  Мета роботи Дослідити роботу операторів функцій мови Паскаль; знати призначення, форму запису та особливості вживання функцій. Освоїти методику розробки, відладки Паскаль-програм (ПП) з використанням функцій на персональних ЕОМ.