Функции | |
def | makeSieve |
Решето Эратосфена. | |
def | MillerRabinTest1 |
Тест Миллера-Рабина. | |
def | MillerRabinTest2 |
Тест Миллера-Рабина. | |
def | test |
Отладочная функция. | |
Переменные | |
powMod = Util.powMod | |
псевдоним для src.fw_1.Util.powMod из src.fw_1.Util. | |
tuple | sieve = makeSieve(1000) |
MillerRabinTest = MillerRabinTest2 | |
псевдоним для src.fw_1.MillerRabin.MillerRabinTest2 из src.fw_1.MillerRabin. |
Теорема Рабина.
Пусть $m$ — нечётное число большее 1.
Число $m-1$ однозначно представляется в виде $m-1 = 2^s \cdot t$, где $t$ нечётно.
Целое число $a$, $1 < a < m$, называется свидетелем простоты числа $m$, если выполняются два условия:
$m$ не делится на $a$; $a^t\equiv 1\pmod m$ или существует целое $k$, $0 <= k<s$, такое, что $ a^{2^kt}\equiv -1\pmod m$
Теорема Рабина утверждает, что составное нечётное число $m$ имеет
не более $\phi(m)/4$ различных свидетелей простоты,
где $\phi(m)$ — функция Эйлера.
использованы стандартные пакеты
random
math
и пакет src.fw_1.Util
def src.fw_1.MillerRabin.makeSieve | ( | n | ) |
Решето Эратосфена.
создадим последовательность длинной n
def src.fw_1.MillerRabin.MillerRabinTest1 | ( | number, | ||
iterations = 10 | ||||
) |
Тест Миллера-Рабина.
Алгоритм частично взят с
http://geo.web.ru/db/msg.html?mid=1161287&uri=node162.html#tests
частично взят из книги Т. Кормана <<Алгоритмы. Построение и Анализ>>
def -- объявление функции
number -- параметр
def src.fw_1.MillerRabin.MillerRabinTest2 | ( | number, | ||
iterations = 7 | ||||
) |
Тест Миллера-Рабина.
Тоже самое что и src.fw_1.MillerRabin.MillerRabinTest1 но более разумная и эффективная реализация
def src.fw_1.MillerRabin.test | ( | ) |
Отладочная функция.
Отладка теста Миллера-Рабина
src::fw_1::MillerRabin.MillerRabinTest = MillerRabinTest2 |
псевдоним для src.fw_1.MillerRabin.MillerRabinTest2 из src.fw_1.MillerRabin.
псевдоним для src.fw_1.Util.powMod из src.fw_1.Util.
простое присваивание функции
tuple src::fw_1::MillerRabin.sieve = makeSieve(1000) |