КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Вероятностный тест Миллера-Рабина
Тест на основе малой теоремы Ферма Малая теорема Ферма утверждает, что если n простое, то выполняется условие: при всех a из {1, 2, …, n −1} имеет место сравнение an −1 ≡ 1 (mod n) (1) Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа a в интервале {1, 2, …, n −1}, то n — составное. Поэтому можно предложить следующий вероятностный тест простоты: выбираем случайное число a из {1, 2, …, n −1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1; если оно не выполняется, то ответ «n — составное»; проверяем выполнимость сравнения (1); если сравнение не выполнено, то ответ «n — составное»; если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз. Числа Кармайкла (Carmichael Numbers) Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (a, n) = 1 верно an-1=1(mod n)
Первые три числа Кармайкла таковы: 561, 1105, 1729. Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много. Пусть n — нечетное и n − 1 = 2 st, t — нечетное. Если число n является простым, то при всех a > 1 выполняется сравнение an −1 ≡ 1 (mod n) Поэтому, рассматривая элементы { at, a 2 t, …, a 2 s −1 t } можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n). На этом замечании основан следующий вероятностный тест простоты: выбираем случайное число a из интервала {1, 2, …, n −1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1; если оно не выполняется, то ответ «n — составное»; вычисляем at (mod n); если at ≡ ±1 (mod n), то переходим к п. 1; вычисляем a 2 t, …, a 2 s −1 t до тех пор, пока не появится −1; если ни одно из этих чисел не равно −1, то ответ «n — составное»; если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз). Составное число не будет определено как составное с вероятностью 1 ⁄ 4. (см. [1]).
Дата добавления: 2013-12-13; Просмотров: 329; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |