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


 

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

42429. Проектирование FM 364 KB
  Ячейка выбираеться по адресу и записываеться по сигналу WR Синхросигнал для ячейки за адресом 000000 Синхросигнал для ячейки за адресом 011001 Синхросигнал для ячейки за адресом 101111 последней 48 ячейки Проектирование однорозрядного триггера: Проектирование разрешения выдачи сигнала: У нас будет три схемы разрешения управляющего сигнала. Схема iтой ячейки FM Общая схема FM.
42430. Проектирование AU 284.5 KB
  Оценить сложность полученной схемы и её быстродействие.C 0100 X 1 C 0000 0000 0000 5 R2 = R2R3 0100 1 0 X 0001 0010 0001 6 R1 = R1 1 0110 1 0 X 0000 xxxx 0000 7 R4=R41 0110 1 0 X 0011 xxxx 0011 2 R5=R1xorR3 0001 0 0 X 0000 0010 0100 Коды операций из 2 лабораторной: 0 0000 P 0011 P 1 0110 P Q 0100 P Q 0001 CIопределяет арифметическая операция или логическаяучитывание переноса F3F2F1F0 код операции F разрешение левого сдвига D сдвигаемый разряд Схема арифметического...
42431. Проектирование СPU 410 KB
  Сигнал F управляет сдвигом ICTR счетчик команд т. длина команды 24 бит счётчик увеличивается на 3 учитывая адрес RM 10битный и счётчик такой же разрядности. IRG регистр команд состоит из 3 байт COP блок управления операциями формирует управляющие сигналы Сi CCRG регистр признаков: Сперенос О переполнение S знак Z ноль. Кодирование и структура команд CPU O LO 4 бита кода МО LSM 4 бита F0F1F2F3 для LSM 2 4битных адреса операндов FM 23 x 24 x 24 = 211 разновидностей операций FR RF 1 бит для направления...
42432. Проектирование СOP 423.5 KB
  В таком случае, COP должен содержать набор логических элементов И-ИЛИ, DC кодов ОР и CTR тактов. Далее выходы И собираются на ИЛИ в соотвествии с формулами для управляющих сигналов. Предполагается, что произведения T2 JC и T2 JC Cc формируются в 2 этапа: 1) в схеме получают сигнал T2 JC. 2) после опроса СС формируют сигналы T2 JC и T2 JC CС.
42433. Соотношение понятий социализации, воспитания и образования. Особенности социализации различных возрастных групп 15.7 KB
  Процесс воспитания – целенаправленный процесс, его цель – накопление ребенком необходимого для жизни в обществе социального опыта, формирование принимаемой обществом системы ценностей и включение детей в мировую и отечественную культуры.
42434. ИЗУЧЕНИЕ СВОБОДНЫХ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА 482.5 KB
  Рассмотрим простейшую колебательную систему: груз массой m, подвешенный на пружине. Если груз, прикрепленный на пружине, оттянуть вниз на некоторое расстояние, а затем отпустить, то он придет в колебательное движение. Возвращение груза в положение равновесия происходит под действием деформированной пружины, т.е. под действием упругой силы
42435. ИЗУЧЕНИЕ ЗАКОНОВ ДВИЖЕНИЯ ЭЛЕКТРОНА В ЭЛЕКТРИЧЕСКОМ И МАГНИТНОМ ПОЛЯХ 279.5 KB
  Начальные скорости электронов эмиссии различны. Это сказывается на характере спада анодного тока. Из-за неодинаковости начальных скоростей электронов радиусы кривизны их траекторий при одних и тех же величинах индукции магнитного поля различны. Поэтому резкий спад анодного тока происходит не при одном значении, а в достаточно широком интервале значений магнитной индукции.
42436. ИЗУЧЕНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ ПРИ ЗАРЯДКЕ И РАЗРЯДКЕ КОНДЕНСАТОРА В ЭЛЕКТРИЧЕСКОМ «R – C» КОНТУРЕ 559 KB
  Расчёт общего вида зависимости напряжения на конденсаторе от времени 5 2. Ветвью называется участок цепи в котором ток в любой данный момент времени имеет одинаковую величину. Расчёт электрических процессов в любой цепи требует умения вычислять зависимости от времени токов в ветвях и напряжения на элементах входящих в...
42437. ЭКСПЕРИМЕНТАЛЬНОЕ ИЗУЧЕНИЕ ЯВЛЕНИЯ ВЗАИМНОЙ ИНДУКЦИИ 272 KB
  Если контур в котором индуцируется ЭДС состоит не изодного витка а из N витков например представляет собойсоленоид то поскольку витки соединяются последовательно будет равна сумме ЭДС индуцированных в каждом витке в отдельности: Величину называют потокосцеплением или полным магнитным потоком. Если поток пронизывающий каждый из витков одинаков то ЭДС индуцируемая в сложном контуре определяется формулой:...