МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» / ТЕСТУВАННЯ ЧИСЕЛ НА ПРОСТОТУ ТА ПОБУДОВА ДОВГИХ ПРОСТИХ ЧИСЕЛ. Практична робота№ 3 Варіант № 9 Львів – 2010р. Мета роботи: вивчити основні програмні методи тестування чисел на простоту. Завдання: Скласти програму, яка б реалізовувала тест Рабіна-Міллера на перевірку простоти числа. Результати роботи подати у звіт. Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення Ev — логічна змінна, яка отримує результат роботи алгоритму Евкліда; rez — логічна змінна, яка отримує результат роботи всієї програми; Evklid () – метод який реалізує алгоритм Евкліда; test () – метод проведення основного тесту; n - змінна, якій присвоюється значення перевіюваного числа; s - змінна, степінь числа 2. t - змінна, непарне число. а - змінна, якій присвоюється випадкове значення; t, x, y - додаткові змінні, що потрібні для роботи методів перевірки. Блок-схема програми: Головний метод Main: Метод Evklid: Метод test: + - Текст Програми: using System; namespace Lab_3_Crupt { class Program { static void Main() { int n = 0; int s = 0; int t = 0; int a = 0; bool Ev, rez; Program ob = new Program(); Console.WriteLine("Записуємо число для перевiрки у вигляді n-1=(2^s)*t:"); n = int.Parse(Console.ReadLine()); Console.WriteLine("Введіть степінь двійки s:"); s = int.Parse(Console.ReadLine()); Console.WriteLine("Введіть число t:"); t = int.Parse(Console.ReadLine()); Random r = new Random(); a = r.Next(1, n - 1); Ev = ob.Evklid(n, a); if (Ev) { rez = ob.test(n, a); if (rez==-1) { Console.WriteLine("Не вiдомо"); Console.ReadLine(); } else { Console.WriteLine("Число складне"); Console.ReadLine(); } } else { Console.WriteLine("Число складне"); Console.ReadLine(); } } public bool test(double x, double y) { Ch1 = (Math.Pow(a,t) –1) % n Ch2 = (Math.Pow(a,t) –(-1)) % n if(Ch1=0 or Ch2=0) { break; void Main(); } else { for(p=1;p<=Math.Pow(2,s-1);p++) { rez=Math.Pow(a,pt)%n } } } public bool Evklid(int x, int y) { int t; while (y != 0) { t = y; y = x % y; x = t; } if (x == 1) return true; else return false; } } } Результат роботи програми: /