4149

Розклад числа на прості множники

Практическая работа

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

Розклад числа на прості множники Означення. Розкладом натурального числа nна прості множники (факторизацією числа) називається представлення його у вигляді взаємно прості числа, ki...

Украинкский

2012-11-13

97.5 KB

4 чел.

Розклад числа на прості множники

Означення. Розкладом натурального числа n на прості множники (факторизацією числа) називається представлення його у вигляді n = , де pi – взаємно прості числа, ki ³ 1 .

Задача перевірки числа на простоту є простішою за задачу факторизації. Тому перед розкладанням числа на прості множники слід перевірити число на простоту.

Означення. Розбиттям числа називається задача представлення натурального числа n у вигляді n = a * b, де a, b – натуральні числа, більші за 1 (не обов’язково прості).

Метод Ферма

Нехай n – складене число, яке не є степенем простого числа. Метод Ферма намагається знати такі натуральні x та y, що n = x2y2. Після чого дільниками числа n будуть a = xy та b = x + y: n = a * b = (xy)(x + y).

Якщо припустити що n = a * b, то в якості x та y (таких що n = x2y2)  можна обрати

,

Приклад. Виберемо n = 143 = 11 * 13.

Тоді x = (13 + 11) / 2  = 12, y = (13 – 11) / 2 = 1.

Перевірка: x2y2 = 122 – 11 = 143 = n.

Теорема. Якщо n = x2y2, то  < x < (n + 1) / 2.

Доведення. З рівності n = x2y2 випливає, що n < x2, тобто  < x.

Оскільки a = n / b, то . Максимальне значення x досягається при мінімальному b, тобто при b = 1. Звідси x =  < .

Отже для пошуку представлення n = x2y2 слід перебрати всі можливі значення x із проміжку [,  (n + 1) / 2], перевіряючи при цьому чи є вираз x2 - n повним квадратом.

Приклад. Розкласти на множники n = 391 методом Ферма.  = 19.

202 – 391 = 9 = 32. Маємо рівність: 391 = 202 – 32.

Звідси 391 = (20 – 3)(20 + 3) = 17 * 23.

Алгоритм Полард - ро факторизації числа

У 1974 році Джон Полард запропонував алгоритм знаходження нетривіального дільника натурального числа n. Пр цьому алгоритм використовує лише операції додавання, множення та віднімання модулярної арифметики.

Ідея алгоритма Полард – ро полягає в ітеративному обчисленні деякої наперед заданої поліноміальної функції f з цілими коефіцієнтами. Побудуємо послідовність xi наступним чином: x0 оберемо довільним із Zn, а xi+1 = f(xi) mod n, i ³ 0. Оскільки xi можуть приймати лише скінченний набір значень (цілі числа від 0 до n), то існують такі цілі n1 та n2 (n1 < n2), що = . Враховуючи поліноміальність f, для кожного натурального k маємо: =, тобто починаючи з індекса i = n1 послідовність {xi mod n} буде періодичною.

Приклад. Нехай n = 21, x0 = 1, xi+1 =  + 3 mod 21.

Тоді послідовність xi має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, ... .

Таким чином x3 = x6, період послідовності дорівнює 3.

Послідовність xi можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру r, тому метод який застосовується в алгоритмі називається r – евристикою. Послідовність із попереднього прикладу можна зобразити так:

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД(x2ixi, n). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n.

Побудуємо послідовність елементів xi наступним чином:

x0 = 2, xi+1 = f(xi) = ( + 1) mod n, i > 0

Алгоритм

Вхід: натуральне число n, параметр t ³ 1.

Вихід: нетривіальний дільник d числа n.

1. a = 2, b = 2;

2. for i ¬ 1 to  t do

2.1. Обчислити a ¬ (a2 + 1) mod n; b ¬ (b2 + 1) mod n; b ¬ (b2 + 1) mod n;

2.2. Обчислити d ¬ НСД(a - b, n);

2.3. if 1 < d < n return (d);  // знайдено нетривіальний дільник

3. return (False);   // дільника не знайдено

Вважаємо, що функція f(x) = (x2 + 1) mod n генерує випадкові числа. Тоді для знаходження дільника числа n необхідно виконати не більш ніж O() операцій модулярного множення.

Якщо алгоритм Поларда – ро не знаходить дільника за t ітерацій, то замість функції f(x) = (x2 + 1) mod n можна використовувати f(x) = (x2 + c) mod n, для деякого цілого c, c ¹ 0, -2.

Приклад. Нехай n = 19939.

Послідовність xi: 2, 5, 26, 677, 19672, 11473, 12391, 6582, 15217, 5483, 15217, 5483, 15217, ... .

a

b

d

2

2

1

5

26

1

26

19672

1

677

12391

1

19672

15217

1

11473

15217

1

12391

15217

157

Знайдено розклад 19939 = 157 * 127.

Нехай n = 143. Послідовність xi: 2, 5, 26, 105, 15, ... .

a

b

d

2

2

1

5

26

НСД(21, 143) = 1

26

15

НСД(11, 143) = 11


Знайдено розклад 143 = 11 * 13.

Ймовірносний квадратичний алгоритм факторизації числа

Твердження. Нехай x та y – цілі числа, x2 º y2 (mod n) та x ¹ ±y (mod n). Тоді x2y2 ділиться на n, при чому жоден із виразів x + y та xy не ділиться на n. Число d = НСД(x2y2, n) є нетривіальним дільником n.

Теорема. Якщо n – непарне складене число, яке не є степенем простого числа, то завжди існують такі x та y, що x2 º y2 (mod n), при чому x ¹ ± y (mod n).

Доведення. Нехай n = n1 * n2 – добуток взаємно простих чисел. Оберемо таке y, що НСД(y, n) = 1. Далі розв’яжемо систему рівнянь:

Розв’язком системи будуть такі x та y за модулем n = НСК(n1, n2), що x2 º y2 (mod n). Якщо при цьому припустити, що x º y (mod n), то з другого рівняння системи маємо: y º y (mod n2), або 2 * y = 0 (mod n2). Оскільки було обрано НСД(y, n2) = 1, то з останньої рівності випливає що n2 ділиться на 2, тобто є парним. Це суперечить умові теореми про непарність n.

Приклад. Виберемо n1 = 11,  n2 = 13 – взаємно прості числа. Тоді n = 11 * 13 = 143. Покладемо y = 5,  НСД(5, 143) = 1. Складемо систему порівнянь:

 або  

Розв’язком системи буде x º 60 (mod 143).

Має місце рівність 602 º 52 (mod 143) , при чому 60 ¹ ±5 (mod 143).

Тоді дільником числа n буде d = НСД(60 – 5, 143) = 11.

Формально ймовірносний квадратичний алгоритм факторизації будується на наступній ідеї:

Нехай F = {p0, p1, p2, …, pt} – множникова основа, pi – різні прості числа, при чому дозволяється обрати p0 = -1. Побудуємо множину порівнянь

 º zi ,

таку що значення zi є повіністю факторизованими у множині F :

,

та добуток деякої підмножини значень zi є повним квадратом:

z =  = y2, y Î Z, fi Î {0, 1}

Якщо множина порівнянь із вказаними властивостями побудована, то поклавши x =  і перевіривши виконання нерівності x ¹ ± y (mod n), отри маємо x2 º y2 (mod n). Число d = НСД(x2y2, n) є нетривіальним дільником n.

Приклад. Знайти дільник числа n = 143.

Обираємо випадково число x Î [2, 142], обчислюємо x2 (mod 143) та розкладаємо результат на множники:

1. z1 = 192 (mod 143) = 75 = 3 * 52.

2. z2 = 772 (mod 143) = 66 = 2 * 3 * 11.

3. z3 = 292 (mod 143) = 126 = 2 * 32 * 7.

4. z4 = 542 (mod 143) = 56 = 23 * 7.

Можна помітити, що добуток z3 та z4 є повним квадратом:

z = z3 * z4 = 24 * 32 * 72 = (22 * 3 * 7)2 = 842

Маємо рівність:

z3 * z4 = 292 * 542 º 842 (mod 143)

або враховуючи що 29 * 54 (mod 143) º 136, маємо:

1362 = 842 (mod 143), при чому 136 ¹ ±84 (mod 143)

Дільником числа n = 143 буде d = НСД(136 – 84, 143) = НСД(52, 143) = 13.

Квадратичний алгоритм факторизації

Серед усіх існуючих алгоритмів факторизації найшвидшим є квадратичний. Він ефективно застосовується для чисел, кількість цифр яких менша за 100 та які не мають малих простих дільників. Еврістичний аналіз, проведений Померансом [1] у 1981 році показав, що число N може бути розкладено на множники за час .

Нехай n – число, яке факторизується, m = . Розглянемо многочлен

q(x) = (x + m)2 - n

Квадратичний алгоритм обирає ai = x + m (x = 0, ±1, ±2, …), обчислює значення bi = (x + m)2n та перевіряє, чи факторизується bi у множниковій основі F = {p0, p1, p2, …, pt}.

Помітимо, що   = (x + m)2n º (x + m)2 (mod n) º bi (mod n).

Алгоритм

Вхід: натуральне число n, яке не є степенм простого числа.

Вихід: нетривіальний дільник d числа n.

1. Обрати множникову основу F = {p0, p1, p2, …, pt}, де  p0 = -1, pii - те просте число p, для якого n є квадратичним лишком за модулем p.

2. Обчислити m = [].

3. Знаходження t + 1 пари (ai, bi).

   Значення x перебираються у послідовності 0, ±1, ±2, … .

   Покласти i ¬ 1. Поки i £ t + 1 робити:

3.1. Обчислити b = q(x) =  (x + m)2n та перевірити, чи розкладається b у множниковій основі F. Якщо ні, обрати наступне x та повторити цей крок.

3.2. Нехай b = . Покласти ai = x + m, bi = b, vi = (vi1, vi2, …, vit), де vij = eij mod 2, 1 £ j £ t.

3.3. i ¬ i + 1.

4. Знайти підмножину T Í {1, 2, …, t + 1} таку що  = 0.

5. Обчислити x =  mod n.

6. Для кожного j, 1 £ j £ t, обчислити lj = () / 2.

7. Обчислити y =  mod n.

8. Якщо x º ±y (mod n), знайти іншу підмножину T Í {1, 2, …, t + 1} таку що  = 0 та перейти до кроку 5.

9. Обчислити дільник d = НСД(xy, n).

Приклад. Розкласти на множники n = 24961.

1. Побудуємо множникову основу: F = {-1, 2, 3, 5, 13, 23}

2. m = [] = 157.

3. Побудуємо наступну таблицю:

i

x

q(x)

факторизація q(x)

ai

vi

1

0

-312

-23 * 3 * 13

157

(1, 1, 1, 0, 1, 0)

2

1

3

3

158

(0, 0, 1, 0, 0, 0)

3

-1

-625

-54

156

(1, 0, 0, 0, 0, 0)

4

2

320

26 * 5

159

(0, 0, 0, 1, 0, 0)

5

-2

-936

-23 * 32 * 13

155

(1, 1, 0, 0, 1, 0)

6

4

960

26 * 3 * 5

161

(0, 0, 1 ,1, 0, 0)

7

-6

-2160

-24 * 33 * 5

151

(1, 0, 1, 1, 0, 0)

4. Виберемо T = {1, 2, 5}, оскільки v1 + v2 + v5 = 0.

5. Обчислимо x = (a1a2a5) (mod n) = 936 = 26 * 34 * 132.

6. l1 = 1, l2 = 3, l3 = 2, l4 = 0, l5 = 1, l6 = 0.

7. y = -23 * 32 * 13 (mod n) = 24025.

8. Оскільки 936 º –24025 (mod n), необхідно шукати іншу множину T.

9. Виберемо T = {3, 6, 7}, оскільки v3 + v6 + v7 = 0.

10. Обчислимо x = (a3a6a7) mod n = 23405 = 210 * 34 * 56.

11. l1 = 1, l2 = 5, l3 = 2, l4 = 3, l5 = 0, l6 = 0.

12. y = -25 * 32 * 53 (mod n) = 13922.

13. 23405 ¹ ±13922 (mod n).

d = НСД(xy, n) = НСД(9483, 24961) = 109 – дільник.

Відповідь: 109 – дільник 24961.

Література

1. Pomerance C. Analysis and comparison of some integer factorization algorithms. In Computational Methods in Number Theory, vol.154, H.Lenstra and R.Tijdeman, Eds. Amsterdam Mathematics Center 1982, pp. 89 – 139.


7

0

19

4

1


 

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

81517. Повреждение и репарация ДНК. Ферменты ДНК-репарирующего комплекса 137.99 KB
  Ферменты ДНКрепарирующего комплекса. Процесс позволяющий живым организмам восстанавливать повреждения возникающие в ДНК называют репарацией. Все репарационные механизмы основаны на том что ДНК двухцепочечная молекула т.
81518. Биосинтез РНК. РНК полимеразы. Понятие о мозаичной структуре генов, первичном транскрипте, посттранскрипционном процессинге 108.48 KB
  РНК полимеразы. В ходе процесса образуются молекулы мРНК служащие матрицей для синтеза белков а также транспортные рибосомальные и другие виды молекул РНК выполняющие структурные адапторные и каталитические функции Транскрипция у эукариотов происходит в ядре.принцип комплементарного спаривания оснований в молекуле РНК G ≡ C =U и Т=А.
81519. Биологический код, понятия, свойства кода, коллинеарность, сигналы терминации 105.17 KB
  Генетический код и его свойства Необходимость кодирования структуры белков в линейной последовательности нуклеотидов мРНК и ДНК продиктована тем что в ходе трансляции: нет соответствия между числом мономеров в матрице мРНК и продукте синтезируемом белке; отсутствует структурное сходство между мономерами РНК и белка. Отсюда становится ясным что должен существовать словарь позволяющий выяснить какая последовательность нуклеотидов мРНК обеспечивает включение в белок аминокислот в заданной последовательности. Он позволяет шифровать...
81520. Роль транспортных РНК в биосинтезе белков. Биосинтез аминоацил-т-РНК. Субстратная специфичность аминоацил-т-РНК-синтетаз 125.71 KB
  У человека около 50 различных тРНК обеспечивают включение аминокислот в белок. тРНК называют адапторные молекулы так как к акцепторному концу этих молекул может быть присоединена определённая аминокислота а с помощью антикодона они узнают специфический кодон на мРНК. В процессе синтеза белка на рибосоме связывание антикодонов тРНК с кодонами мРНК происходит по принципу комплементарности и антипараллельности.
81521. Последовательность событий на рибосоме при сборке полипептидной цепи. Функционирование полирибосом. Посттрансляционный процессинг белков 111.26 KB
  Каждая эукариотическая мРНК кодирует строение только одной полипептидной цепи т. она моноцистронна в отличие от прокариотических мРНК которые часто содержат информацию о нескольких пептидах т. Кроме того на полицистронных мРНК синтез белка начинается до того как заканчивается их собственный синтез так как процессы транскрипции и трансляции не разделены.
81522. Адаптивная регуляция генов у про- и эукариотов. Теория оперона. Функционирование оперонов 127.06 KB
  Регуляция активности генов у прокариотов. В экспериментах гипотеза оперона получила полное подтверждение а предложенный в ней тип регуляции стали называть контролем синтеза белка на уровне транскрипции так как в этом случае изменение скорости синтеза белков осуществляется за счёт изменения скорости транскрипции генов т. Согласно теории Жакоба и Моно оперонами называют участки молекулы ДНК которые содержат информацию о группе функционально взаимосвязанных структурных белков и регуляторную зону контролирующую транскрипцию этих генов.
81523. Понятие о клеточной дифференцировке. Изменение белкового состава клеток при дифференцировке (на примере белкового состава полипептидных цепей гемоглобина) 105.05 KB
  Дифференцировка клеток определенного типа сводится к экспрессии в них комплекса генов специфичных для данной клеточной линии. Экспрессия этих генов в свою очередь контролируется регуляторными районами гена промоторами и энхансерами. Энхансеры регуляторные районы ДНК расположенные на некотором расстоянии от контролируемых ими генов но в том же локусе хромосомы. Для того чтобы промоторы и энхансеры тканеспецифических генов могли взаимодействовать с ТФ они должны быть открытыми т.
81524. Молекяулрные механизмы генетической изменчивости. Молекулярные мутации: типы, частота, значение 110.08 KB
  Молекулярные мутации: типы частота значение Классификация мутаций Тип мутаций Характер мутационных изменений Примеры последствий Геномный Изменение числа хромосом Болезнь Дауна появление дополнительной хромосомы 21 Хромосомные Общее число хромосом не меняется. Частота мутаций в половых клетках высока. Основные виды генных мутаций Виды мутаций Изменения в структуре ДНК Изменения в структуре белка ЗАМЕНА Без изменения смысла кодона Замена одного нуклеотида в кодоне Белок не изменён С изменением смысла кодона миссенсмутация ...
81525. Генетическая гетерогенность. Полиморфизм белков в популяции человека (варианты гемоглобина, гликозилтрансферазы, группоспецифических веществ и др) 107.01 KB
  Группы крови. Другой важный пример полиморфизма белков связанный с проблемой переливания крови существование в популяции людей 3 аллельных вариантов гена фермента гликозилтрансферазы А В и 0. Антитела к антигенам А и В обычно имеются в сыворотке крови людей на поверхности эритроцитов которых отсутствует соответшвующий антиген т. индивидуумы с антигенами А на поверхности эритроцитов продуцируют в сыворотку крови антитела к Вантигенам антиВ а люди с Вантигенами антитела к антигенам А антиА.