Элементы теории чисел и криптозащита. Воронков Б.Н - 75 стр.

UptoLike

Составители:

Рубрика:

Рис. 3

3. Если Вы знаете, как написать графические программы, то попро-

буйте изобразить многоугольник для различных значений

р и k, проверяя

результат пункта (2), а также постарайтесь оценить насколько редки случаи,

когда при

m = n многоугольник невозможно замкнуть.

20. Тесты на простоту

Главное применение идеи порядка мы сделаем здесь для тестирования

выбранных целых чисел на простоту. Вообще говоря, результаты проверки

на простоту числа

n зависят от возможности представить число в виде про-

изведения некоторых чисел, близко расположенных от

n, например, п ± 1.

Представим образец, который даёт представление теоремы Ферма в очень

специфическом случае.

20.1. Теорема (простота 2р + 1). Предположим, что р – простое чис-

ло и пусть

n = 2p + 1. Если 2

n-1

≡ 1 (mod n) и 3 не делит n, тогда n будет

простым числом