Программная реализация алгоритма первообразные корни (нахождение первообразного корня)

Размещено на http://www.allbest.ru/

Введение

Существует большое количество практических задач, рассмотрение которых сводится к изучению нахождение первообразного корня.

Первообразный корень по модулю n называется такое число g, что все его степени по модулю n пробегают по всем числам, взаимно простым с n. Математически это формулируется таким образом: если g является первообразным корнем по модулю n, то для любого целого a такого, что gcd (a, n) = 1, найдётся такое целое k, что a ( mod n ). В частности, для случая простого с n степени первообразного корня пробегают по всем числам от 1 до n-1. Другими словами, первообразный корень - это образующий элемент мультипликативной группы кольца с вычетов по модулю n.

Первообразные корни для простых p были введены Эйлером, но существование первообразных корней для любых простых модулей p было доказано лишь Гауссом в 1801 году.



Постановка задачи

алгоритм первообразный корень

Разработать программу на С++ в консольном приложении, реализующую алгоритм нахождения первообразного корня.

- информационные сообщения и запросы: программа должна указывать пользователю, что необходимо сделать на данном этапе или какое действие произошло.

- ввод необходимых данных: положительное натуральное число, натуральная степень от 1 до 10 и положительно натуральный модуль (данные вводятся пользователем с клавиатуры в ответ на запросы программы, отражающиеся на экране).

- обработка данных: в процессе работы алгоритма программы функция powmod() выполняет бинарное возведение в степень по модулю, а функция generator ( int p) - находит первообразный корень по простому модулю p ( факторизация числа (n) здесь осуществлена простейшим алгоритмом за О()).

- вывод результата на экран в числовом виде.

- завершение программы пользователем.

- если пользователь ввел не корректные данные, программа выводит сообщение об ошибке и предоставляет повтор ввода данных.

Входная информация

Входной информацией в алгоритме Первообразного корня являются число, ограниченная степень от 1 до 10 и модуль для которого мы ищем первообразную корня.



Выходная информация

На выходе программа должна вывести на экран число, которое и будет первообразной корня для введенного модуля или сообщение об отсутствии первообразного корня для введенного модуля.

Основные понятия

Первообразный корень по модулю n называется такое число g, что все его степени по модулю n пробегают по всем числам, взаимно простым с n. Математически это формулируется таким образом: если g является первообразным корнем по модулю n, то для любого целого a такого, что gcd (a, n) = 1, найдётся такое целое k, что a ( mod n ). В частности, для случая простого с n степени первообразного корня пробегают по всем числам от 1 до n-1. Другими словами, первообразный корень - это образующий элемент мультипликативной группы кольца с вычетов по модулю n. Мультипликативная группа кольца вычетов. Приведённая система вычетов по модулю m - множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m-1.

Основные сведения об алгоритме

Первообразные корни для простых p были введены Эйлером, но существование первообразных корней для любых простых модулей p было доказано лишь Гауссом в 1801 году.

Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедится, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:



Существование алгоритма

Первообразный корень по модулю n существует тогда и только тогда, когда n является либо степенью нечётного простого, либо удвоенной степенью простого, а также в случаях n=1, n=2, n=4.

Теорема

Пусть g - первообразный корень по модулю p . Тогда - первообразный корень по модулю p НОД ( a; p-1) =1. НОД - Наибольший Общий Делитель.

Доказательство

Так как - первообразный корень, значит (, но p , поэтому (p) = p-1, значит (, и это же справедливо для g:. Пусть НОД (a; p-1) = k, k>1, тогда 1 = .Но, по определению org, p-1 - минимальная степень, в которую следует возвести , чтобы получить единицу, a. Получили противоречие, теорема доказана.

Техническое задание. Назначение разработки

Получение практических и теоретических навыков разработки программного обеспечения в рамках курсовой работы по дисциплине "Технология Программирования".



Основная идея

Автоматизация метода нахождения первообразного корня для введенного модуля.

Программное обеспечение, необходимое для реализации проекта

Для программной реализации данного проекта используется среда разработки программного обеспечения Microsoft Visual Studio 2010.

Требование к функциональным характеристикам

Программная система должна обеспечивать работу с функциями и указателями на функции

Функциональные характеристики

Система должна обеспечивать возможность выполнения следующих функций:

1) Ввод необходимой информации;

2) Обработку введенной информации;

3) Вывод результата обработки;

Исходные данные:

1) Число;

2) Степень от 1 до 10;

3) Модуль.

Результаты:

1) Первообразный корень.



Требования к надежности

Предусмотреть контроль вводимой информации.

Предусмотреть блокировку некорректных действий пользователя при работе с программой.

Состав и параметры технических средств

Система должна работать на IBM совместимых персональных компьютерах.

Минимальная конфигурация:

тип процессора -- Pentium и выше;

объем оперативного запоминающего устройства -- 32 Мб и более.

Требования к информационной и программной совместимости

Система должна работать под управлением семейства операционных систем Win 32 (Windows 7, Windows 95, Windows 98, Windows 2000, Windows NT и т. п.).

Требования к программной документации

Разрабатываемые программные модули должны быть самодокументированы, т. е. тексты программ должны содержать все необходимые комментарии.

В состав сопровождающей документации должны входить:

Пояснительная записка на 20-30 листах, содержащая описание разработки;

Руководство системного программиста;

Руководство пользователя;

Апробация.

Руководство программиста

Программа написана на языке C++ в среде разработки Microsoft Visual Studio 2010. Программа является консольным приложением.

Используем в программе библиотеки

#include "stdafx.h" //стандартная библиотека

#include <iostream> //библиотека ввода вывода

#include <Windows.h> //подключает русский язык

#include <stdio.h> //стандартный заголовочный файл ввода/вывода

#include <vector> //стандартная библиотека реализующая динамический массив произвольного доступа

#include <math.h> //простые математические операции

Инициализация элементов

using namespace std; //использует пространство имен

int phi(int ); //функция Эйлера в переменной phi

int powmod(int, int, int); //функция бинарного возведения в степень по модулю

int generator (int ); //находит первообразный корень

int d, a, b, p = 0;//переменный для хранения введенных данных

int error = 0;//переменная для вывода ошибки

//Фунция Эйлера

//функция вычисляет Наибольший Общий делитель

int phi (int n)

{

int result = n;

for (int i=2; i*i<=n; ++i)

if (n % i == 0)

{

while (n % i == 0)

n /= i;

result -= result / i;

}

if (n > 1)

result -= result / n;

return result;

}

Запрос данных

//ввод данных

do

{

try

{

printf("В ведите положительное натуральное число: ");

scanf("%i", &a);

if(a<0)

{

error = 1;

throw 1;

}

else

{

error = 0;

}

}

catch(int er)

{

printf("Ошибка! Число должно быть натуральное и положительное!\n");

}

}while(error == 1);

do

{

try

{

printf("В ведите натуральную степень от 1 до 10: ");

scanf("%i", &b);

if(b>10||b<1)

{

error = 1;

throw 1;

}

else

{

error = 0;

}

}

catch(int er)

{

printf("Ошибка! Степень должна быть от 1 до 10!\n");

}

}while(error == 1);

do

{

try

{

printf("В ведите натуральный положительный модуль: ");

scanf("%i", &p);

if(p<0)

{

error = 1;

throw 1;

}

else

{

error = 0;

}

}

catch(int er)

{

printf("Ошибка! Модуль должен быть натуральным и положительным!\n");

}

}while(error == 1);

Реализация алгоритма Первообразного корня

//Выполняет бинарное возведение в степень по модулю

int powmod (int a, int b, int p)

{

int res = 1;

while (b)

if (b & 1)

res = int (res * 1ll * a % p), --b;

else

a = int (a * 1ll * a % p), b >>= 1;

return res;

}

//Находит первообразный корень по простому модулю р

int generator (int p)

{

vector<int> fact; //динамический массив для факториала

int phi = p-1, n = phi; //функция пробегающая по всем числам от 1 до n-1

for (int i=2; i*i<=n; ++i)

if (n % i == 0)

{

fact.push_back (i);//помещает факториал в конец

while (n % i == 0)

n /= i;

}

if (n > 1)

fact.push_back (n);

for (int res=2; res<=p; ++res)

{

bool ok = true;

for (size_t i=0; i<fact.size() && ok; ++i)

ok &= powmod (res, phi / fact[i], p) != 1;

if (ok) return res;

}

return -1;//если нет первообразного корня, передает в результат -1

}



Вывод результата

d=generator(p);//передает в переменную d, первообразную из функции

if(d == -1)//если нет первообразной, то вместо значения -1, выводим сообщение

printf("Первообразного корня для этого модуля нет\n\n", d);

else

printf("Первообразный корень равен: %i\n\n", d);

system("pause");

Руководство пользователя. Общие сведения о программе

Алгоритм Первообразного корня - программа предназначена для вычисления первообразного корня по данным которые вводит пользователь.

Данная программа может использоваться в математике для вычисление первообразного корня.

Установка программы не требуется. Запуск осуществляется двойным нажатием левой кнопки мыши по иконке программы.

Инструкция по работе

После запуска программы появляется окно:

Рисунок 5.2.1 - Вид программы после запуска

На все запросы программы пользователь должен отвечать вводом с клавиатуры запрашиваемого числового значения.

Пользователю предлагается ввести натуральное число. После ввода числа, программа запрашивает степень от 1 до 10 и модуль.

Рисунок 5.2.2 - Ввод всех данных

После ввода всех данных программы выводит результат.

Рисунок 5.2.3 - Вывод результата

После завершения работы для выхода из программы можно воспользоваться «красным крестиком» или любую клавишу на клавиатуре.

Апробация

Для проверки работоспособности программы воспользуемся примером приведенным на википедии.

Пример:

Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедится, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:



Вводим число 3, степень 1 и модуль 7:

Рисунок 6.1 - Результат работы программы

Вводим число 2, степень 2 и модуль 7:

Рисунок 6.2 - Результат работы программы

Вводим число 6, степень 3 и модуль 7:



Рисунок 6.3 - Результат работы программы

Вводим число 4, степень 4 и модуль 1:

Рисунок 6.4 - Результат работы программы



Заключение

В процессе создания данного проекта разработана программа, реализующая алгоритм Первообразного корня в Microsoft Visual Studio 2010. Программа работает в консольном режиме.

В ходе работы над курсовым проектом было выполнено следующее:

Описаны важные теоретические моменты, опираясь на которые была составлена постановка задачи к курсовой работе.

В соответствии с поставленной задачей разработан и реализован алгоритм в виде программы по изученной теме.

Разработано руководство программиста, в котором отражены важные моменты реализации алгоритма. Каждый смысловой блок программы имеет пояснение, а также внутренние комментарии.

Разработано руководство пользователя, в котором описаны общие сведения о программе и инструкция по работе.

Проведена проверка работоспособности программы на примерах из электронного пособия и проверка ввода некорректных значений. В результате ответы на сайте и ответы, полученные программой, совпали. Также программа осуществляет контроль над тем, чтобы пользователь вводил только корректные данные.



Список используемых источников

1. Герберт Шилдт. C++ для начинающих -- Москва, Эком, 2007 г.- 640 с.

2. Павловская Т. А. С/С++. Программирование на языке высокого уровня. Учебник для вузов -- Спб.: Питер 2003. -- 461 с.

3.Первообразный корень [Электронный ресурс] : энциклопедия -- Режим доступа: ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел). -- Загл. с экрана.

4.Мультипликативная группа кольца вычетов [Электронный ресурс] : энциклопедия -- Режим доступа: ru.wikipedia.org/wiki/Мультипликативная_группа_кольца_вычетов . -- Загл. с экрана.

Размещено на Allbest.ru

...