БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ ИРАДИОЭЛЕКТРОНИКИКафедра информатикиПояснительная записка к курсовому проекту
по курсу
«Архитектура вычислительных систем»
на тему
«Планирование работ в вычислительныхсистемах по критерию минимального суммарного времени выполнения работ»
МИНСК, 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 longa, 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
x1 = (x1*x1 + 1) % N;
i++;
y = x1 — x;
d = NOD(y, N);
if (d != 1)
{
cout
cout
N/=d;
i = 1;
x = 0;
}
}
while (N != 1);
getch();
}