10045

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

Доклад

Информатика, кибернетика и программирование

Тестирование чисел на простоту случайные и детерминированные тесты. Тест малой теоремы Ферма При использовании асимметричных криптосистем возникает необходимость построения сверхбольших псевдослучайных простых чисел. Соответствующие вычислительные процедуры

Русский

2013-03-20

46 KB

24 чел.

Тестирование чисел на простоту, случайные и детерминированные тесты. Тест малой теоремы Ферма

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

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

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

Существует два типа критериев простоты: детерминированные и вероятностные. Детерминированные тесты позволяют доказать, что тестируемое число – простое.

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

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

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

Примером вероятностного теста является тест на основе малой теоремы Ферма. Эта теорема утверждает, что если - простое, то для всех , взаимно простых с , выполняется условие (сравнение Ферма): . Таким образом, если условие теоремы Ферма не выполнено хотя бы для одного числа в интервале , то - составное.

Тест на основе малой теоремы Ферма заключается в следующем.

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

Назовем нечетное составное число псевдопростым по основанию  , если пара удовлетворяет сравнению .

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

Следовательно, вероятность ошибки может не снижаться, лишь если является псевдопростым для всех (ненулевых) оснований. Тем не менее, такие числа существуют. Они называются числами Кармайкла. Например, числом Кармайкла является число .

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


 

А также другие работы, которые могут Вас заинтересовать

78156. Социализация личности. Семейное воспитание 52.23 KB
  Признаки и функции коллектива методика его формирования. Признаки развитого коллектива: наличие общественно и личностно значимых целей; включение членов коллектива в разнообразную социальную деятельность; соответствующая организация совместной деятельности; связь коллектива с обществом; наличие положительных традиций и перспектив; атмосфера взаимопомощи доверия и требовательности; развитые критика и самокритика сознательная дисциплина и др. Это результат упорного целенаправленного и длительного труда всего коллектива результат...
78157. Социальная подструктура личности 33.17 KB
  Стадии социализации личности. Полученные в процессе социализации знания приобретенные личностные качества не станут лишь индивидуальным достоянием а станут достоянием общества так как человек не только обогащается опытом но и реализует себя как личность влияя на жизненные обстоятельства и окружающих людей. Механизмы социализации: Имитация механическое повторение воспроизведение наблюдаемых человеком социальных действий без понимания их подлинного смысла.
78158. Эмоции и психические состояния личности 115.54 KB
  Эмоции имеются и у животных но у человека они приобретают особую глубину имеют множество оттенков и сочетаний. Эмоции различают по интенсивности и длительности а также по степени осознанности причины их появления. В связи с этим выделяют: настроение собственно эмоции и аффекты.
78159. Биологическая и психологическая подструктуры личности 129.43 KB
  Механизмы развития и тренировки памяти. Этот образ соотносится с информацией хранящейся в памяти и мотивационными установками человека. информированность индивида об объекте представлений и продолжительность сохранения его образов: представления памяти т. Особенности памяти: память немыслима без других психических процессов так как она запечатляет сохраняет и воспроизводит психические продукты этих процессов когда мы воспринимаем чтото оно запоминается; память это сквозной психический процесс так как присутствует в течение...
78160. Введение в курс «Основы психологии» 196.17 KB
  Психология и очень старая и совсем молодая наука. Начало превращения психологии в самостоятельную науку связывают с именем немецкого ученого Христиана Вольфа 1679-1754 опубликовавшего книги Рациональная психология 1732 и Экспериментальная психология 1734 в которых он использовал термин психология. психология окончательно выделилась в самостоятельную науку. Возникли такие ее отрасли как педагогическая юридическая военная управленческая спортивная психология и т.
78162. Личность и группа как субъект и объект управления 49.27 KB
  Особенности коммуникации в организации. И это в полной мере относится и к личности и к организации в качестве субъектов и объектов управления. Управление личностью может складываться из: правильного определения социальной роли каждого работника и его места в организации; усвоения каждым индивидом предназначенной ему роли; обеспечения выполнения каждым работником своей роли. Нормы служат ориентиром личности в ситуации выбора обеспечивают социальный контроль ее поведения а также упорядочивают характер взаимодействий в рамках организации...
78163. Личность и творчество 55.97 KB
  Одной из важнейших задач современной педагогики является формирование у человека способности быть творцом что позволит ему достигнуть успехов в различных видах деятельности. Для реализации и развития субъекта в творческой деятельности и в частности для развития его творческого потенциала необходимым условием является свобода. При организации творческой деятельности важное значение имеет степень активности субъекта творчества. Творческая активность это мотивированная готовность личности к творческой деятельности определяемая скоростью...
78164. Межличностные отношения и взаимодействия людей в малых группах 63.18 KB
  Понятие малой группы. Социальнопсихологический климат группы. Социометрическая структура группы. Социальная роль всегда несет на себе печать общественной оценки: общество может либо одобрять либо не одобрять некоторые социальные роли иногда одобрение или неодобрение может дифференцироваться у разных социальных групп оценка роли может приобретать совершенно различное значение в соответствии с социальным опытом той или иной общественной группы.