Разработка программного продукта в среде Visual C++, осуществляющего генерацию псевдослучайных чисел двумя методами

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

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

Введение

В современном стремительно развивающемся информационном обществе достаточно остро стоит вопрос хранения и передачи информации. Несмотря на непрерывно возрастающий накопительный объем информационных носителей, порой требуется сохранить большое количество данных на хранилище небольшой емкости (например, флэш-накопителе). Для уменьшения размеров применяются особые алгоритмы - так называемые алгоритмы сжатия. Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию - он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифpованию, что затрудняет поиск шифpа доступным для взломщика статистическим методом. Существует достаточно большое количество их всевозможных вариаций. В данной работе будут рассмотрены основные сведения об архивации и типах сжатия, а так же - приведены реализация алгоритма LZ77 на языке программирования С++.

Microsoft Visual Studio -- линейка продуктов компании Microsoft, включающих интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения, так и приложения с графическим интерфейсом.

Microsoft Visual C++ (MSVC) -- интегрированная среда разработки приложений на языке C++, разработанная фирмой Microsoft и поставляемая либо как часть комплекта Microsoft Visual Studio, либо отдельно в виде бесплатного функционально ограниченного комплекта Visual C++ Express Edition. Сменила интегрированную среду разработки Microsoft Quick C.

1. Цели курсовой работы

Целью данной курсовой работы является получение знаний по выбранной тематике и создание программного продукта в среде Visual C++, осуществляющего генерацию псевдослучайных чисел двумя методами.

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

- осуществлять интерфейс с пользователем,

- генерировать псевдослучайное число.

2. Литературный обзор

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

Задача: создать программный продукт на языке C++, осуществляющий генерацию псевдослучайных чисел.

Подзадачи:

• Изучить существующие методы генерации.

• Выбрать метод генерации, исходя из параметров эффективности, быстродействия и простоты реализации.

• Создать программный продукт.

• Провести тестирование программного продукта.

2.2 Описание предметной области

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

Современная информатика широко использует псевдослучайные числа в самых разных приложениях -- от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов.

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

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается -- начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2n/2, где n -- размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n. Если порождаемая последовательность ГПСЧ сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

• Слишком короткий период/периоды.

• Последовательные значения не являются независимыми.

• Некоторые биты «менее случайны», чем другие.

• Неравномерное одномерное распределение.

• Обратимость.

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

Линейный конгруэнтный метод применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.

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

Регистр сдвига с линейной обратной связью (LFSR) -- регистр сдвига битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

3. Обзор выбранного метода

Хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким. Генераторы на основе линейного конгруэнтного метода являются предсказуемыми, поэтому их нельзя использовать в криптографии. Впервые генераторы на основе линейного конгруэнтного метода были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar). Ей удалось также вскрыть квадратические и кубические генераторы. Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Таким образом, была доказана бесполезность генераторов на основе конгруэнтных методов для криптографии. Однако генераторы на основе линейного конгруэнтного метода сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики.

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

Преимущества:

• высокое быстродействие криптографических алгоритмов, создаваемых на основе РСЛОС (например потоковых шифров);

• применение только простейших битовых операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах;

• хорошие криптографические свойства (РСЛОС могут генерировать последовательности большого периода с хорошими статистическими свойствами);

• благодаря своей структуре, РСЛОС легко анализируются с использованием алгебраических методов.

Недостатки:

• Одна из главных проблем РСЛОС в том, что их программная реализация крайне неэффективна: приходится избегать разреженных многочленов обратной связи, так как они приводят к облегчению взлома корреляционным вскрытием, а плотные многочлены очень медленно просчитываются. Поэтому программная реализация такого генератора работает не быстрее, чем реализация DES.

• Линейность последовательности на выходе регистра позволяет однозначно определить многочлен обратной связи C(x) по 2L последовательным битам с помощью алгоритма Берлекэмпа -- Мэсси или алгоритма Евклида.

• Относительная лёгкость анализа алгебраическими методами не только облегчает разработку, но и увеличивает шансы на взлом генератора на базе РСЛОС.

4. Программная реализация

4.1 Назначение

Программа «Курсовой проект: Генерация псевдослучайных чисел» предназначена для осуществления генерации псевдослучайных чисел.

4.2 Пользовательский интерфейс

Рис. 1

Основное окно программы:

При запуске программы:

• Отображается тема курсовой работы.

• Программа предлагает одно из действий в меню.

4.2 Пример использования

Рис. 2. Выбрать `M'

Рис. 3. Выбрать `1'

Рис. 4. Выбрать `2'

Рис. 5. Выбрать `0'

Рис. 6. Выбрать `D' и ввести начало и конец диапазона чисел

Рис. 7. Выбрать `M'

Рис. 8. Выбрать `1'

Рис. 9. Выбрать `2'

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

Рис. 10. Выбрать `0'

Рис. 11. Выбрать `S' и ввести имя файла

Рис. 12. Файл `1.txt'

4.3 Листинг программного кода

Interface.cpp

#include <stdio.h> // библиотека ввода-вывода

#include <locale.h> // библиотека языковой локализации

#include "global.h" // библиотека работы с упакованным числом

#include <cstdio>// для вывода в файл

// Длинаименифайла

static const int length = 66;

#pragma warning(disable: 4996)

/*

Главная функция. Реализует ввод, проверку, интерфейс с пользователем.

*/

int PrintСongruential(int min, int max);

int PrintLFSR (int min, int max);

void main()

{

int ch = '\0';// Пунктменю

int fl0 = 0,fl1 = 0, fl2 = 0, fl = 0;// Проверка на использование метода

long int min = 0, mmin = -2147483648;// Min диапазона

long int max = 100, mmax = 2147483647;// Max диапазона

int level;// Компонента уровня

bool direct;// Компонента направления

char filename[length];// Имя файла

FILE *fp;// Указатель на файловой поток

// Для сообщений на русском языке

setlocale(LC_ALL, "Russian");

printf("Курсавая работа: Генератор псевдослучайных чисел");

do { // Цикл обработки команд

switch(ch)

{

case 'M': // Выборметода

case 'm':

do {

// Отобразитьподменю

printf("\n\nПодменю<Выбор метода>:");

printf("\n1. Линейный конгруэнтный метод");

printf("\n2. Метод регистра сдвига с линейной обратной связью");

printf("\n0. Вернуться в главное меню");

printf("\nВыберите подпункт:>");

fflush(stdin);

ch = getchar();

switch(ch)

{

case '1': // Печать ленейно конгруэнтного метода

X1 = PrintСongruential(min, max);

fl1 = 1;

fl2 = 0;

break;

case '2': // Печать метода регистра сдвига с линейной обратной связью

X2 = PrintLFSR(min, max);

fl1 = 0;

fl2 = 1;

break;

}

}

while(ch != '0');

break;

case 'D': // Настройка диапазона случайных значений

case 'd':

do{

// Ввести длину диапазона и проверить корректность ввода

printf("\nВведите диапазон случайных чисел [-2147483648..2147483647]:>");

printf("min = ");

scanf("%ld", &min);

printf("max = ");

scanf("%ld", &max);

// Проверить корректность ввода и допустимоть диапазона

if(min < mmin || min > mmax - 1 ||

max < mmin + 1 || max > mmax)

{

printf("Ошибка: Некорректныйдиапазон:\n");

if(min < mmin || min > mmax - 1) printf("Проблемас min\t");

if(max < mmin + 1 || max > mmax) printf("Проблемас max\t");

fl0 = 1;

}

if(min >= max)

{

if(min > max) printf("\nmax долженбытьбольше min\t");

if(min == max) printf("max и min должны иметь разные значения\t");

fl0 = 1;

}

}

while(fl0 == 1);

break;

case 'S': // Сохранение числа в файле

case 's':

fflush(stdin);

// Ввести имя файла

printf("\nВведите имя файла для сохранения (или нажмите [enter] для отмены):>");

if(*gets_s(filename, length) == '\0') break;

// Создать файл для сохранения массива

if((fp = fopen(filename, "w")) == NULL)

printf("\nОшибка: Файл с указанным именем не может создан или открыт на запись\n");

else

{

if(ch == 's' || ch == 'S')

{

// Записать последнее сгенерированное чисело в текстовый файл

if(fl1 == 1) fprintf(fp, "%ld", X1);

else {

if(fl2 == 1) fprintf(fp, "%ld", X2);

else {

fl = 1;

fprintf(fp, "Число не было сгенерировано");

}

}

}

// Закрыть файл

fclose(fp);

if(fl == 0) printf("\nЧисло сохранен успешно\n");

else printf("\nЧисло не было сохранено\n");

}

break;

case '\0': // Пустая команда

break;

default:

printf("Ошибка: Некорректная операция");

break;

};

// Сбросить устройство ввода

fflush(stdin);

// Отобразить главное меню

printf("\n\nГлавное меню:");

printf("\nM. Выбор метода");

printf("\nD. Ввод диапазона случайных чисел(по умолчанию 0..100)");

printf("\nS. Сохранение последнее сгенерированное чисело в текстовом файле");

printf("\nQ. Выход");

printf("\nВыберите пункт:>");

ch = getchar();

}

while((ch != 'Q') && (ch != 'q'));

// Сохранение новых сгенерированных чисел

freopen("Global.h", "w", stdout);

printf("static unsigned long X1 = %d;\nstatic unsigned long X2 = %d;", X1, X2);

}

PrintLFSR.cpp

#include <stdio.h> // библиотекаввода-вывода

#include "global.h" // библиотека работы с упакованным числом

int PrintLFSR (int min, int max)

{

X2 = ((((X2 >> 31) (X2 >> 6) (X2 >> 4) (X2 >> 2)

(X2 >> 1) X2) & 0x00000001) <<31) | (X2 >> 1);

printf("Сгенерированноечисло: %d\n", X2 % (max - min) + min);

return X2;

}

PrintСongruential.cpp

#include <stdio.h>// библиотека ввода-вывода

#include"Global.h"// библиотека работы с упакованным числом

int PrintСongruential(int min, int max)

{

X1 = (16807 * X1 + 1) % 2147483647;

printf("Сгенерированное число: %d\n", X1 % (max - min) + min);

return X1;

}

Global.h

static unsigned long X1 = 1;

static unsigned long X2 = 1;

Заключение

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

Линейный конгруэнтный метод и метод РСЛОС показали хорошую эффективность при высоком быстродействии и относительной простоте реализации. Эти алгоритмы очень удобны для Генерации псевдослучайных чисел.

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

...