Было принято решение разработать тестовые задания для проверки работы алгоритмов, реализованных студентами. Данные тестовые задания представляют из себя наборы тестовых данных, используя которые студент может оценить правильность работы реализованного им алгоритма. В качестве примера таких тестовых данных приведем данные, предложенные студенту в главе «Вероятностные тесты на простоту» к тесту Ферма. Тестовые данные оформлены в виде таблицы. В первой колонке данной таблицы присутствует описание чисел, которые представлены во второй колонки. В третьей колонке представлен результат теста при проверки чисел из второй колонки.
Первая апробация методического пособия проходила в апреле 2008 года в институте Математики и компьютерных наук ТюмГУ на специальности «Компьютерная безопасность» (группы 347, 348) в рамках курса «Криптографические методы защиты информации». К моменту апробации пособие содержало только два раздела: вероятностные тесты на простоту» и «Доказуемо простые числа». Каждый раздел содержал теоретический материал по данному разделу, а именно описание алгоритмов тестов на простоту и задания для выполнения к каждому разделу. Студентам двух групп (347 и 348 группа) на протяжении двух лабораторных занятий (4 учебных часа) давались задания из второго и третьего разделов методического пособия. При выполнении этих заданий студенты пользовались лекционным материалом и теоретическим материалом из методического пособия. Задания выполнялись ими в аудитории под руководством преподавателя, а также во время, отведенное для самостоятельной работы.
Результаты сдавались в виде таблиц, приведенных в заданиях к лабораторным работам. Кроме того, для проверки и анализа были собраны исходные коды программ, реализованных студентами.
Кроме того, студенты были опрошены на предмет того, какие моменты в реализации алгоритмов генерации простых чисел вызывали затруднение. Оказалось, что 7 из 11-ти человек, выполнявших генерацию простых чисел с помощью теста Соловея-Штрассена, затруднялись в исполнении программной реализации вычисления символа Якоби, который используется в данном тесте. Это тем более неожиданно, что большинство студентов достаточно уверенно вычисляют подобные символы самостоятельно (при помощи ручки и бумаги). Поэтому было решено включить в текст пособия алгоритм вычисления символа Якоби. 6 из 11-ти студентов, реализовывавших тест Миллера-Рабина, заявили о необходимости примера в тексте пособия, демонстрирующего работу алгоритма. Такой пример был добавлен в пособие.
Студенты, выполнявшие задания по генерации простых чисел при помощи тестов Миллера и Поклингтона (1-й и 2-й варианты), затруднялись в построении числа p – кандидата в простые числа. Дело в том, что число p должно быть случайным, нечетным, и при этом каноническое разложение числа (p—1) должно быть известно. 18 из 22-х студентов, выполнявших 1-й и 2-й варианты, заявили о необходимости осветить в тексте пособия вопрос создания такого числа подробнее. Поэтому в текст пособия были включены инструкции по генерации таких чисел.
Кроме того, анализ текстов программ показал, что общим местом является неоптимальное выполнение арифметических операций на больших числах, которые используются в тестах. В частности, алгоритм возведения в степень у 19 из 33 студентов был реализован через последовательное умножение. Небольшое количество студентов (5 чел.) обращались к преподавателю за помощью, поскольку при возведении числа в степень по модулю (akmodn) получали переполнение буфера. Оказалось, что все эти студенты пытались сначала возвести число в степень, и лишь затем вычислить остаток от деления на n. Такого рода ошибки, возникающие из-за недопонимания процессов, происходящих в памяти компьютера при выполнении арифметических операций, встречались достаточно часто, что послужило побудительным мотивом к включению в пособие раздела «Операции с большими числами», включающего в себя теоретический материал, задания к лабораторным работам.
В целом, апробация пособия в ТюмГУ прошла успешно, студенты справились с предложенными им заданиями, в текст пособия были внесены необходимые изменения, несколько изменилась подача материала.
Апробация пособия в ТГФЭУП проводилась в рамках преддипломной практики в период с сентября по декабрь 2008 года. На апробацию пособия руководством вуза было выделено 10 часов аудиторной нагрузки. В апробации участвовали студенты пятого курса специальности «Прикладная информатика в экономике». Дисциплина «Криптографические методы защиты информации» не является профильной на данной специальности, а выступает в качестве специального курса. На момент апробации методическое пособие содержало три главы: «Операции с большими числами», «Вероятностные тесты на простоту», «Доказуемо простые числа» также задания для лабораторных и самостоятельных работ.
Апробация проводилась по той же схеме что и в ТюмГУ. Студентам двух групп на протяжении двух занятий преподавателем было предложено выполнить первую лабораторную работу, т.е. реализовать класс для работы со 128битными числами. Изначально преподаватель объяснил студентам общетеоретический материал касающейся данной темы и реализовал совместно с ними операцию сложения, а остальные операции было предложено реализовать самостоятельно. В ходе эксперимента выяснилось, что студенты имеют слабое представление о представлении чисел в памяти компьютера, что в свою очередь потребовало дополнительных объяснений. Несмотря на то, что операцию сложения студенты делали под руководством преподавателя, довольно распространенной ошибкой стала ошибка связная с битом переноса. У студентов данной специальности отсутствует в программе дисциплина «Теория чисел», поэтому перед тем как приступить к заданиям второй главы преподавателю пришлось прочитать лекцию (в частности о практическом применении Асимптотического закона распределения, вычислении символа Якоби и символа Лежандра и.т.д.). Несмотря на то что студентов ознакомили с теоретическим материалом непосредственно перед выполнением лабораторной работы студенты затруднялись в применении асимптотического закона при генерации простых чисел. В результате анализа лабораторных работ второй главы встречались разнообразные ошибки, но данные ошибки были настолько разные, что не представлялось возможным обледенить их в общие группы. Несмотря на то, что на апробацию пособия руководством вуза было выделено 10 часов, нам не удалось апробировать третью главу пособия, это связано с тем, что преподавателю приходилось отклоняться от темы работы и объяснять сопутствующий материал из других дисциплин. В целом апробация прошла успешно, в пособие были внесены некоторые корректировки. Также было принято решение включить в пособие тесты для самопроверки для каждой из глав, что позволило бы студенту проверять правильность выполненных им работ без участия преподавателя.
Результатом данной дипломной работы является методическое пособие довольно полно и подробно освещающее тему генерации больших простых чисел. Поставленная цель - разработать методическое пособие на тему «Генерация простых чисел» для специальности «Компьютерная безопасность» Тюменского государственного университета, включающее в себя теоретический материал, задания к практическим работам, указания к их выполнению и материалы для проверки качества выполненных заданий, достигнута в полном объеме.
Материал, изложенный в пособии, является вполне достаточным для выполнения работ, поскольку все необходимые алгоритмы описаны и приведены примеры. Материал изложен не в общетеоретическом вида, а в виде инструкций и алгоритмов, что позволяет студенту выполнять лабораторные работы, не обращаясь к другим источникам литературы.
Данное пособие подходит как для контактного аудиторного обучения, так и для внеаудиторного обучения, что придает ему некоторую гибкость, т.е. оно может использоваться не только на специальностях, на которых «Криптографические методы защиты информации» является обязательной дисциплиной с выделенном аудиторным временем, но и для специальностей, где данная дисциплина изучается в рамках специализированного курса. Также данное пособие может выступать в качестве дополнительной литературы при освоении данной темы студентами других специальностей (таких как специальность «математика»). Поскольку оно позволяет не только дистанционно обучаться, но и позволяет преподавателю дистанционно проверять задания, выполненные студентом (это достигается путем использования таблиц результатов). Кроме того, данные для самопроверки позволяют студенту проверить корректность выполненных им работ без участия преподавателя.
В результате прочтения студентом теоретической части, изложенной в пособии, студент должен получить следующие знания:
· знание об основных принципах создания класса больших чисел и работы с ним;
· знание о способах получения простых чисел;
· знание о теоретико-числовых принципах, на которых основаны тесты на простоту;
· знание об асимптотическом законе распределения простых чисел;
· знание о надежности тестов, об их быстродействии;
· знания о том, что не все числа определенные детерминистическими тестам как составные на самом деле таковыми являются;
· представление о различии вероятностных и детерминистических тестов на простоту (студент будет иметь четкое представление о том, что при реализации детерминистических тестов он строит число, простота которого не вызывает сомнений).