С какой вероятностью должен вычисляться делитель составного числа в подпрограмме для нахождения факторизации числа:

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

Вероятность получения ответа " - составное" для алгоритма проверки простоты составного числа n равна:

Какова вероятность получить делитель числа в результате работы процедуры нахождения делителя ( - число различных простых делителей ):

Алгоритм проверки простоты числа с вероятностью выдает ответ:

Условием выхода из алгоритма проверки простоты числа является:

Проверка простоты числа является классическим примером задачи класса:

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

В соответствии с алгоритмом Евклида, если делить большее число на меньшее, то длина записи меньшего числа уменьшается на константу:

Как называется порядок числа в мультипликативной группе вычетов

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