Міністерство освіти і науки України Національний університет ″Львівська політехніка″ Кафедра захисту інформації
Звіт про виконання лабораторної роботи №3 з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ” на тему: “Тестування чисел на простоту та побудова довгих простих чисел. Факторизація складених чисел” Перевірив: Лагун А.Е. Львів 2009 Мета роботи: засвоїти основні програмні методи тестування чисел на простоту, а також прості алгоритми факторизації складного числа. Завдання : а) Генерація простих чисел; б) Розклад довільного числа на прості множники. Блок -схема головної програми  SHAPE \* MERGEFORMAT початок Vsi prosti chusla, cho ne perevuch. 256: s=s+1 s i=2…256;i++ q=2…i;q++ (i%q)=0 ні так i!=q так ні i vvedit dovilne chuslo p=,p “p=” p%2=0 1,2 так ні
  SHAPE \* MERGEFORMAT 2,1 “*2” p=p/2 j <=p так ні p%j==0 так ні j p=p/j j=j+2 кінець
 Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах , та їх пояснення i, j, q– цілі змінні, що використовуються в циклi. p – ціла змінна, що містить значення, що розкладають на прості множники. s – ціла змінна, що містить суму значень простих чисел на певному інтервалі. Остаточна версія програми #include <stdlib.h> #include <stdio.h> int main() { int i, q,p,j=3,s=0; printf ("Vsi prosti chusla, cho ne perevuch. 256:\n"); for(i=2;i<=256;i++) {for(q=2;q<=i;q++) { if((i%q)==0) if(i!=q) { break; } else { printf("%5d", i); s++; } } } printf("\n n=%d ", s); printf("\nvvedit dovilne chuslo p="); scanf("%d",&p); printf("%d=",p); while(p%2==0) { printf("%d*",2); p=p/2; } while(j <=p) { if(p%j==0) { printf("%d*",j); p=p/j; } else j=j+2; } system("PAUSE"); return 0; } Результат роботи програми