Читайте также:
|
Функция Мёбиуса мультипликативна: для любых взаимно простых чисел a и b выполняется равенство μ(ab) = μ(a)μ(b).
Сумма значений функции Мёбиуса по всем делителям целого числа n, не равного единице, равна нулю
Из этого в частности следует что для всякого непустого конечного множества количество различных подмножеств состящих из нечётного числа элементов равно количеству различных подмножеств состоящих из чётного числа элементов — факт, применяемый в доказательстве формулы обращения Мёбиуса.
Функция Мёбиуса связана с функцией Мертенса отношением
17.. Проверка простоты чисел.
В криптографии сильным называется простое число p, такое что:
1. p достаточно велико
2. p − 1 имеет достаточно большие простые делители, то есть q 1 в p = a 1 q 1 + 1
3. q 1 − 1 имеет достаточно большие простые делители, то есть q 2 в q 1 = a 2 q 2 + 1
4. p + 1 имеет достаточно большие простые делители
Иногда также добавляют дополнительные условия, например a 1 = 2, a 2 = 2 и т.п.
Решето Эратосфена. следующий метод построения всех простых чисел, не превосходящих некоторого заданного числа N. Берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает └ √N┘, то работу прекращаем, поскольку все оставшиеся числа являются простыми.
Данный метод позволяет строить множество простых чисел, но он не удобен для проверки простоты заданного числа. (Необходимо проверить делимость n на числа 2, 3, 5, 7, … √n. Сложность О(√n)) Тем не менее идея решета и ее обобщения в настоящее время часто используются для просеивания множеств чисел, обладающих тем или иным условием.
Тест на основе малой теоремы Ферма. Малая теорема Ферма утверждает, что если n простое, то выполняется условие:
При всех аÎ{2, 3,…n-1} имеет место сравнение an-1=1mod n. (1) Обратное утверждение неверно. Из этой теоремы следует, что если сравнение (1) не выполнено хотя бы для одного числа а в интервале {2, 3,…n-1}, то n – составное. Поэтому можно предложить следующий вероятностный тест простоты:
1. выбираем случайное число из интервала {2, 3,…n-1}, и проверяем с помощью алгоритма Евклида условие (a, n)=1;
2. если оно не выполняется, то ответ «n - составное»;
3. проверяем выполнимость сравнения (1);
4. если сравнение не выполнено, то ответ «n - составное»;
5. если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз.
Если выполняется сравнение (1), то говорят, что число n является псевдопростым по основанию а. Заметим, что существует бесконечно много пар чисел (a, n), где n - составное и псевдопростое по основанию а. Числа для которых условие (1) выполняется для всех оснований называются числами Кармайкла. (561, 1105, 1729) Таким образом, при применении рассмотренного теста возможны три ситуации:
1. число n простое и тест всегда говорит «не известно»;
2. число n составное и не является числом Кармайкла; тогда с вероятностью успеха не меньше ½ однократный тест дает ответ «n составное»;
3. число n составное и является числом Кармайкла, тогда тест всегда дает ответ «не известно».
Наличие третьей ситуации является очень неудобным свойством данного теста. Для практики нужны тесты, в которых третья ситуация не возникает.
Дата добавления: 2015-12-01; просмотров: 25 | Нарушение авторских прав