51418

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

Доклад

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

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

Русский

2014-02-11

386.5 KB

14 чел.

Раздел 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


 

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

31103. Собственность, выбор, конкуренция 97.5 KB
  Собственность и хозяйствование Собственность – это общественная форма присвоения факторов и результатов производства. Основополагающую роль играют отношения собственности на факторы производства. Экономическое содержание собственности на факторы производства – это способ их соединения который может быть прямым или опосредованным отношениями найма. Особая важность экономической категории собственности определяется тем что: собственность является основой всей системы экономических отношений; от отношений собственности зависит положение...
31104. Товар и деньги 32 KB
  Сущность денег Существует две теории возникновения денег: рационалистическая и эволюционная. Классическая теория денег рассматривает деньги как законченную форму всеобщего эквивалента в качестве которого выступают драгоценные металлы: золото и серебро. В соответствии с классической теорией денег они выполняют функции меры стоимости средства обращения средства накопления средства платежа мировых денег. Современная денежная система характеризуется господством бумажнокредитных денег.
31105. Затраты и результаты 63.5 KB
  В экономической теории и практике различают понятия затраты и издержки производства. Поэтому издержки производства зависят и от уровня затрат во многом обусловленных используемой технологией и от цен на ресурсы. В краткосрочном периоде часть издержек фирмы остается постоянной в долговременном периоде все издержки являются переменными зависящими от объема выпуска. Средние величины: средние общие АТС средние постоянные АFС и средние переменные VC издержки используются в принятии решений в текущем и будущих периодах.
31106. Рынок. Сущность рынка и его функции 100 KB
  Рыночная экономика – это такая экономическая система, в которой решения принимаются самостоятельными экономическими субъектами децентрализовано на основе свободы выбора. Рынок – это форма взаимоотношений между экономическими субъектами: продавцами и покупателями
31107. Спрос как экономическая категория. Факторы, оказывающие влияние на изменение спроса 80 KB
  Факторы оказывающие влияние на изменение спроса Механизм рынка делает производителей – участников конкурентного процесса заинтересованными в удовлетворении потребностей но только тех которые выражаются через спрос. Индивидуальный – спрос отдельного покупателя характеризуется ценой спроса и величиной объемом спроса. Цена спроса – это максимальная цена по которой покупатель еще способен приобрести данный товар. Объем спроса это максимальное количество конкретного товара которое покупатель готов приобрести в рассматриваемом периоде...
31108. Основные положения теории потребительского поведения 64.5 KB
  Основные положения теории потребительского поведения Теория потребительского поведения исходит из совокупности гипотез: о свободе выбора и суверенитете потребителя о рациональности потребителя. Первая из гипотез означает не только наличие права и возможности для потребителя выбирать желаемое благо но и способности воздействовать на производителя. Таким образом суверенитет потребителя проявляется в возможности влиять на производителя через выражение своего отношения к товару его количеству и качеству. Теория рационального поведения...
31109. Макроэкономическая нестабильность: безработица и инфляция 40.77 KB
  Определенный уровень безработицы считается нормальным или оправданным.Уровень безработицы – процентное отношение незанятых к рабочей силе ккоторой не относятся студенты пенсионеры заключенные а также юноши идевушки до 16 лет.Общий уровень безработицы – процентное отношение безработных к общейрабочей силе включающей лиц занятых на действительной военной службе. ТИПЫ БЕЗРАБОТИЦЫ Фрикционная безработица Если человеку предоставляется свободы выбора рода деятельности и местаработы в каждый данный момент некоторые работники оказываются...
31110. Финансы и финансовая политика государства 40.07 KB
  Финансы Российской Федерации это экономические отношения по созданию распределению и использованию фондов денежных средств государства его территориальных подразделений а также предприятий и организаций необходимых для обеспечения расширенного воспроизводства и социальных нужд в процессе которых происходит распределение и перераспределение совокупного общественного продукта и контроль за удовлетворением общественных потребностей. Совокупность входящих в состав финансов Российской Федерации звеньев в их взаимосвязи образуют финансовую...
31111. Денежный рынок и денежно-кредитная политика государства 185.53 KB
  Деньги и их функции Деньги представляют собой всеобщее средство платежа при покупке товаров и услуг а также при уплате налогов других обязательных платежей. Как правило в каждой стране имеются свои деньги национальная валюта которая вводится государством. По своей природе деньги например рубль являются долговой распиской обязательством центрального банка страны обеспеченным всеми его активами. Деньги выполняют ряд функций.