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


 

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

78499. Развитие креативности младших школьников в условиях игровой деятельности 123.53 KB
  Развитие креативности младших школьников в условиях игровой деятельности Актуальность исследования проблемы креативности детей младшего школьного возраста обусловлена необходимостью развития творческих качеств личности созданием условий для формирования основных компонентов творческого мышления. Задача развития креативности общей способности к творчеству стоит и перед первой образовательной ступенью начальной школой. Развитие креативности имеет свои особенности в каждом возрастном периоде причем различные факторы влияющие на...
78500. Арт-техники в практике индивидуальной работы психолога с подростками 1.03 MB
  Рисунок который был сделан на первой встрече называется Мое настроение рисунок. Кате сначала было сложно включиться в работу но когда она сосредоточилась то быстро изобразила рисунок на предложенную тему. Она работала старательно и помощи ей не потребовалось в течение всего занятия она ясно поняла что и как надо сделать. Рисунок полученный в результате был очень темным и скудным по своей экспрессии и имел диагностический характер.
78501. Влияние научно – исследовательской деятельности старшеклассников на развитие креативности 43.82 KB
  Влияние научно исследовательской деятельности старшеклассников на развитие креативности Креативность является сравнительно новой психологической характеристикой появившейся в психологии в начале 50х гг. Исследования креативности за рубежом начались раньше чем в России. Активно разрабатываются и адаптируются западные диагностические методики измерения креативности на российских выборках. Исследование креативности и организации школьных научных обществ с различных точек зрения больше носит теоретико-эмпирический характер и имеет...
78502. Развитие креативности в старшем школьном возрасте 67.58 KB
  Развитие креативности в старшем школьном возрасте На современном этапе в российском обществе в социально-экономической сфере науке технике происходят глобальные изменения. Научный интерес вызывают концепции креативности Дж. Цель исследования: изучение специфики и особенностей развития креативности в старшем школьном возрасте. Предмет исследования процесс развития креативности в старшем школьном возрасте.
78503. Развитие художественного интереса учащихся старших классов на материале музееведения 382.5 KB
  Вся идеология работы с подрастающим поколением должна строиться на культуре, традициях, эстетическом воспитании и художественном развитии. Очень важно, чтобы подрастающее поколение совершенствовалось и развивалось не только в музыкальном, литературно-художественном плане
78505. Психологические факторы готовности студентов к развитию интеллектуальной сферы школьников 53.43 KB
  В современных условиях интеллектуальному развитию школьников придаётся особое значение наряду с другими развивающими целями и задачами обучения. Развитие интеллектуальной сферы школьников рассматривается многими исследователями как условие пронизывающее весь учебный процесс. В этой связи своевременным становится вопрос о специальной подготовке будущих учителей к работе по развитию интеллектуальной сферы школьников.
78506. Решение психологических задач как средство повышения качества профессиональной подготовки воспитателей дошкольных образовательных учреждений 60.47 KB
  В преподавании психологии могут применяться задачи на установление соответствия между теоретическими понятиями и закономерностями и примерами их использования задачи по психологическому анализу поведения литературных героев или известных людей задачи по психологическому анализу частных жизненных или учебных ситуаций и др. Первоначальные попытки создать задачи по психологии работы А. Задачи широко используются при изучении общей возрастной педагогической психологии в вузах Сборник задач по общей психологии 1974; Ф. Задачи по детской...
78507. Психологическая компетентность воспитателя дошкольного образовательного учреждения 64.96 KB
  В психологии общепринятой является точка зрения согласно которой понятие компетентность включает знания умения навыки а также способы выполнения деятельности. Огарев понимает компетентность как устойчивую способность к деятельности со знанием дела. Автор отмечает что компетентность является категорией оценочной и характеризует человека как субъекта специализированной деятельности где развитие способностей человека дает ему возможность выполнять квалифицированную работу принимать ответственные решения в проблемных ситуациях...