Пакет src.MillerRabin

Тут находится тест Миллера-Рабина. Подробнее...


Функции

def makeSieve
 Решето Эратосфена.
def MillerRabinTest1
 Тест Миллера-Рабина.
def MillerRabinTest2
 Тест Миллера-Рабина.
def test
 Отладочная функция.

Переменные

 powMod = Util.powMod
 псевдоним для src.Util.powMod из src.Util.
tuple sieve = makeSieve(1000)
 MillerRabinTest = MillerRabinTest2
 псевдоним для src.MillerRabin.MillerRabinTest2 из src.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.Util


Функции

def src.MillerRabin.makeSieve (   n  ) 

Решето Эратосфена.

создадим последовательность длинной n

def src.MillerRabin.MillerRabinTest1 (   number,
  iterations = 10 
)

Тест Миллера-Рабина.

Алгоритм частично взят с
http://geo.web.ru/db/msg.html?mid=1161287&uri=node162.html#tests
частично взят из книги Т. Кормана <<Алгоритмы. Построение и Анализ>>
def -- объявление функции
number -- параметр

def src.MillerRabin.MillerRabinTest2 (   number,
  iterations = 7 
)

Тест Миллера-Рабина.

Тоже самое что и src.MillerRabin.MillerRabinTest1 но более разумная и эффективная реализация

def src.MillerRabin.test (  ) 

Отладочная функция.

Отладка теста Миллера-Рабина


Переменные

псевдоним для src.MillerRabin.MillerRabinTest2 из src.MillerRabin.

псевдоним для src.Util.powMod из src.Util.

простое присваивание функции

tuple src::MillerRabin.sieve = makeSieve(1000)


Документация по FW_1. Последние изменения: Mon Mar 30 07:24:11 2009. Создано системой  doxygen 1.5.5