Главная Учебники - Разные Лекции (разные) - часть 33
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И
РАДИОЭЛЕКТРОНИКИ по курсу «Архитектура вычислительных систем» на тему «Планирование работ в вычислительных
системах по критерию минимального суммарного времени выполнения работ» МИНСК, 2001 Факторизовать целое число N с
помощью ро-метода Полларда. Целое число N. Ро-метод Полларда для факторизации
заключается в следующем: 1.
Составляется последовательность {x}, xi+1=f(xi), f(x)=x2+1 2.
Вычисляются разности yi= x2i- xi 3.
Вычисляется наибольший общий
делитель чисел yi и N. Если он больше 1, полученный НОД (yi , N) является делителем числа N. Если нет –
продолжаем выполнение алгоритма сначала. - Ввод числа N. - Пока N не равно 1: 1.
Вычисление xi 2.
Вычисление x2i 4.
Нахождение разности yi=
x2i- xi 3.
Вычисление НОД (yi
, N) 4.
Проверка НОД (yi , N) на равенство 1. Если это условие выполняется, то НОД
– один из делителей числа N. Делим N на НОД и переходим к началу
цикла. Выход из цикла – равенство числа N
единице. #include "stdio.h" #include "conio.h" #include "iostream.h" unsigned long NOD(unsigned long
a, unsigned long b) { while ((a > 0) && (b
> 0)) if (a > b) a %= b; else b %= a; if (a == 0) return b; return a; } void main() { unsigned long N, y, x, x1, i,
j, d; clrscr(); printf("Введите N : "); scanf("%ld", &N); i = 1; x = 0; do { x = (x*x + 1) % N; x1 = x; for (j = 0; j < i*2-i; j++) x1 = (x1*x1 + 1) % N; i++; y = x1 - x; d = NOD(y, N); if (d != 1) { cout<<"Делитель :
"<<d<<" "; cout<<"Кол-во шагов : "<<i-1<<endl; N/=d; i = 1; x = 0; } } while (N != 1); getch(); }
|