БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики Пояснительная записка к курсовому проектупо курсу
«Архитектура вычислительных систем»
на тему
«Планирование работ в вычислительных системах по критерию минимального суммарного времени выполнения работ»
МИНСК, 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();
}
Похожие работы
... риск развития заболевания. На основании полученной оценки руководство диспетчерского центра ввело в штатное расписание второго диспетчера. Место и роль маневрового диспетчера наливной станции таковы, что он обязан осуществлять принцип единоначалия. Необходимо создать для диспетчера такие условия, чтобы его загрузка оставалась в пределах нормы. В условиях новой информационной технологии рабочее ...
... приведения к базовому узлу, метод удельных весов, метод учета затрат на единицу веса изделия, расчет себестоимости по статьям затрат. В данном проекте приводится расчет себестоимости разработки автоматизированной системы управления торговым предприятием. (АСУТП). АСУТП служит для ведения учета торговой деятельности в Интернет и на аукционе EBay. Из основных преимуществ перед конкурентами стоит ...
... телеги, микропроцессорные системы и т.д. В данном дипломном проекте поставлена задача оптимизировать сборку телеги, а также выявить экономический эффект за счет инноваций технологии и экономии ресурсов. Рассмотрим основные составляющие телеги: - Полка ТМ.201.01.03 – 24 шт. – Лист Б-О-ПН-2,0 ГОСТ 19903-74/12Х18Н10Т ГОСТ 5582-75; - Заглушка ТМ.201.01.09 – ...
... исполнители высокой квалификации; это вполне может быть осуществлено в короткие сроки силами службы эксплуатации. Использование вторичных энергоресурсов для нагрева теплоносителей в системах отопления, вентиляции и кондиционирования воздуха. Использование вторичных энергоресурсов (ВЭР) для теплоснабжения промышленных зданий приобретает все большие масштабы. Экономически это вполне оправдано – ...
0 комментариев