Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
4. Как отличить составное число от простогоСуществует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число N простое, то для любого целого а, не делящегося на
Если же при каком-то а это сравнение нарушается, можно утверждать, что пытаться найти необходимое число а, испытывая все целые числа подряд, начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке К сожалению, такой подход не всегда дает то, что хотелось бы. Имеются составные числа В 1976 г. Миллер предложил заменить проверку (9) проверкой несколько иного условия. Детали последующего изложения можно найти в [8]. Если
делится на Пусть а) N не делится на а; Р)
Из сказанного ранее следует, что для простого числа N не существует хороших чисел а. Если же N составное число, то, как доказал Рабин, их существует не менее Теперь можно построить вероятностный алгоритм, отличающий составные числа от простых.
|
1 |
Оглавление
|