rsa-python/primalityMillerRabin.py at master · jacksjm/rsa-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from random import randrange
from genericsFunctions import MDC
from genericsFunctions import MDCEst
from genericsFunctions import testMod

def primalityMillerRabin( nParamTest ):
	nTrial = 1
	nNumTrial = 20
	nNumTest = nParamTest

	# Casos distintos, valida as casos bases
	if nParamTest == 3:
		return True
	if nParamTest == 5:
		return True
	if nParamTest == 7:
		return True

	if nParamTest <= 10:
		return False

	# Reduz d até um número ímpar
	nReduct = nParamTest - 1
	while ( nReduct % 2 == 0):
		nReduct = nReduct // 2

	# Executa o teste a quantidade de vezes definida
	while nTrial <= nNumTrial:
		nTrial += 1
		if not millerRabinTest(nReduct,nParamTest):
			return False
	return True

def millerRabinTest(nReduct,nParamTest):

	nAleatory = randrange(2, nParamTest - 4 )# Busca um número aleatório entre 2 e o Valor - 4

	nPow = testMod(nAleatory,nReduct,nParamTest)# Executa a potência modular

	# Caso a potência modular for 1 ou o valor - 1 indica que é primo
	if (nPow == 1 or nPow == nParamTest - 1):
		return True

	# Caso não seja, reduz até encontrar o valor
	while ( nReduct != ( nParamTest - 1 ) ):
		nPow = nPow * nPow % nParamTest
		nReduct = nReduct * 2

		if (nPow == 1):
			return False

		if (nPow == ( nParamTest - 1 ) ):
			return True