Метод Монте-Карло 2 Пусть m --- целое число, которое мы раскладываем на множители. Оно представимо в виде произведения степеней простых чисел m = p1^e1 p2^e2 ... pk^ek Предположим, что p1 - 1 представимо в виде произведения степеней простых чисел, причем каждая из этих степеней не очень велика. Более точно, существует N такое, что p1 - 1 = q1^a1 q1^a2 ... qr^ar q1^a1 < N, q2^a2 < N, ..., qr^ar < N. Рассмотрим всевозможные максимальные степени простых чисел, не превосходящие N. Например, пусть N = 20, тогда рассматриваются степени простых 16, 9, 5, 7, 11, 13, 17, 19. Обозначим эти степени простых через t1, t2, ..., ts. Выберем произвольное целое число b. Рассмотрим последовательность b0 = b, b1 = b0^t1 (mod m), b2 = b1^t2 (mod m), ... bs = b_{s-1}^ts (mod m) Каждый раз, вычислив bi, вычисляем одновременно НОД(bi - 1, m). Утверждается, что с большой вероятностью на каком-то шаге этот НОД будет нетривиальным делителем N. Действительно,покажем, что p | НОД(bs - 1, m). Действительно, bs = b^(t1 t2 ... ts), и, поскольку по предположению, p1 - 1 | t1 t2 ... t3, то есть t1 t2 ... ts = (p1 - 1)g, то bs = b^(t1 t2 ... ts) = b^((p1 - 1) g) = (b^(p1 - 1))^g = 1 (mod p1) по малой теореме Ферма. Значит, bs - 1 делится на p1, число m также делится на p1, следовательно, НОД(bs - 1, m) делится на p1. Проиллюстрируем алгоритм на простом примере. Возьмем N = 20. Выпишем все степени простых, не превосходящие 20: t1 = 16, t2 = 9, t3 = 5, t4 = 7, t5 = 11, t6 = 13, t7 = 17, t8 = 19. Попытаемся разложить на множители число m = 41779 = 41 * 1019. Выберем b = 2. Последовательно вычисляем 2 ^ 16 (mod 41779) = 23757, gcd(23757 - 1, 41779) = 1, 23757 ^ 9 (mod 41779) = 7970, gcd(7970 - 1, 41779) = 1, 7970 ^ 5 (mod 41779) = 33580, gcd(33580 - 1, 41779) = 41. Мы получили нетривиальный делитель на третьем шаге, поскольку 41 - 1 = 8 * 5 делит (t1 * t2 * t3) = 16 * 9 * 5. Мощность алгоритма зависит от числа N --- чем больше оно, тем большие числа можно разложить с помощью этого алгоритма. Работа алгоритма разбивается на 2 шага. Сначала мы генерируем все максимальные степени простых чисел, не превосходящие N. Этот шаг выполняется только один раз и не зависит от входного числа m, поэтому сгенерированные степени можно, к примеру, записать в файл и в дальнейшем использовать многократно. Затем мы выбираем случайным образом число b и вычисляем указанную выше последовательность степеней b. Для каждой степени bi вычисляется НОД(bi - 1, m). Алгоритм завершается успешно, если вычисленный НОД нетривиален. Алгоритм можно убыстрить, если вычислять НОД не на каждом шаге, а, скажем, на каждом сотом шаге. При этом на промежуточных шагах последовательно вычисляется произведение (b_i - 1) (b_{i+1} - 1) (b_{i+2} - 1) ... (b_{i+99} - 1) = n (mod m) и затем вычисляется НОД(n, m). <<<  Назад  1  2   8  Комментарии к статье  8 8  Обсудить в чате