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


 

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

70327. Полимерные композиционные материалы: методы получения 48.2 MB
  Методические указания содержат теоретические основы получения получения ПКМ различными методами применяемые эпоксидные смолы и отвердители описание получения ПКМ методом вакуумной инфузии в лаборатории которое необходимо выполнить практически.
70328. Стресс и адаптация: Учебно-методическое пособие 302.88 KB
  Настоящее учебно-методическое пособие составлено в соответствии с требованиями учебных программ по нормальной физиологии и предназначено для самостоятельной работы студентов при подготовке к занятиям и экзаменам, при решении тестовых и ситуационных задач.
70329. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ «ФИЗИЧЕСКАЯ КУЛЬТУРА» 1.61 MB
  Целью физического воспитания студентов является формирование физической культуры личности и способности направленного использования разнообразных средств физической культуры, спорта и туризма для сохранения и укрепления здоровья, психофизической подготовки и самоподготовки...
70330. ИСТОРИЧЕСКИЕ ОБРАЗЫ ФИЛОСОФСКОЙ МЫСЛИ 738.5 KB
  Философия как новый тип мировоззрения, сменивший мифологическое мировосприятие, возникает в 6 в. до н.э. одновременно в трех относительно изолированных друг от друга регионах тогдашнего древнего мира: на Востоке – в Древнем Китае и Древней Индии и на Западе – в Античной Греции.
70331. Программирование на алгоритмическом языке Паскаль 644.5 KB
  Переменные снабжаются именами, которые могут содержать латинские буквы, цифры и знаки подчеркивания, но начинаться имя должно с буквы. Программист выбирает имена произвольно, но таким образом, чтобы они указывали на смысл переменной.
70332. Средневековая философия 1014.5 KB
  Ариане не принимали основной догмат официальной христианской церкви, согласно которому бог-сын единосущен богу-отцу. По учению Ария, сын божий Логос (Христос) — творение бога, следовательно, не единосущен ему, т. е. в сравнении с богом-отцом является существом низшего порядка.
70333. Словарь терминов по средневековым школам и университетам 95 KB
  Диспут (лат. disputatio) – в схоластической системе образования средневековой Европы формальный способ ведения спора, проводимого с целью установления богословской или научной истины. Данный процесс подчинялся формальным правилам, основными из которых были ссылки устоявшиеся...
70334. Терминология средневековой литературы 22.65 KB
  Канцона буквально песня лирическая форма средневековой поэзии возникшая первоначально в феодально-рыцарской лирике Прованса откуда она была усвоена французскими и итальянскими подражателями.
70335. СЛОВАРЬ ТЕРМИНОВ И ПОНЯТИЙ ПО ИСТОРИИ СРЕДНЕВЕКОВОГО ИЗОБРАЗИТЕЛЬНОГО ИСКУССТВА 2.61 MB
  Йоркский собор (англ. York Minster) — готический собор в английском городе Йорке, который оспаривает у Кёльнского собора звание самого большого средневекового храма на севере Европы. Строительство началось в 1220 году и продолжалось 250 лет. Собор славится самыми большими витражными окнами средневековой Европы.