Ainda falando em primos – Python
No último post sobre números primos, citei uma forma que ainda utiliza fatoração, que não é uma maneira rápida de se descobrir se um número é ou não primo, apesar das várias formas de "pular" alguns números.
Como voltei a ler o livro Algoritmos do Dasgupta, Sanjoy et al. achei mais uma forma de se fazer isso pulando a parte chata da fatoração.
Essa formula se baseia no fato que para todo número primo p e todo a, 1<= a < p tem a seguinte afirmação como verdade:
a^( p - 1 ) mod p = 1 mod p
Dessa forma pode-se evitar a fatoração que é algo absurdamente lento. Em python ficaria da seguinte forma:
def primo( num ): if( 2**(num-1) % num == 1 % num): print "primo" else: print "nao primo"
O problema do teorema é que ele não afirma que "se e somente se" a igualdade for verdadeira teremos um número primo, ou seja, poderia haver números compostos que passariam no teste. E existem. Os números de Carmichael passam no teste e por isso, de acordo com a wikipedia, eles também são chamados de pseudoprimos. Porém eles são raros e dependendo de tão grande é o primo que você necessita, como na criptografia RSA, vale a pena o risco de se usar um pseudoprimo ao invés de fatorar um número gigantesco.
Além disso, existem casos em que o valor de a também deixaria a igualdade verdadeira para números compostos, Sanjoy afirma que metade dos valores possíveis de a fazem isso se desconsiderarmos os números de Carmichael.
Uma forma de se evitar falsos positivos é testar o número com diferentes e aleatórios valores para a. Quanto mais testes, menor é a probabilidade de erro. Testar 100 valores para a faria com que seja mais fácil um raio cósmico queimar o computador do que obter um falso positivo, brinca Sanjoy.
Exponenciação Modular
Durante o projeto de criptografia do semestre passado, tivemos várias dificuldades para trabalhar com números grandes. Desde a limitação do long(contornamos usando BigInteger no java) a vagarosidade de se trabalhar com exponenciação modular.
Para evitar que x^y crescesse demais a ponto de ficar incalculável, resolvemos multiplicar x mod N, y vezes. Porém ainda assim o algoritmo era lento. No livro de Algoritmos do Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani, temos um exemplo muito mais prático que toma o tempo de O(log² N) que é multiplicar por potências que correspondem aos 1 da representação binária de y. Exemplo:
x^25 = x^11001 = x^16 * x^8 * x^1
Em python:
def exponenciacao(x,y,n):
if y == 0:
return 1
z = exponenciacao(x,y/2,n)
if y % 2 == 0:
return (z**2) % n
else:
return ( x*z**2 ) % n
Soma de 1 até n inteiros
Estou lendo um livro sobre a teoria dos números e um dos princípios básicos do livro é a regra de soma de n inteiros positivos. Para somar de 1 até n basta seguir a regra:
S(n) = n * ( n -1 )
Exemplo:
S(3) = 3 * ( 3-1 )
S(3) = 3 * 2
S(3) = 6 = 1 + 2 +3
Implementado em python:
Função totiente de Euler – Python
Estou trabalhando em um trabalho de criptografia para a universidade e precisava saber o phi do produto de dois primos. O phi deste número é bem simples de se conseguir, basta subtrair os dois primos por um, aqui chamados de p e q, e multiplica-los( (p - 1) x (q - 1) ). Exemplo em python usado no algoritmo:
# http://eliasgranja.com def phi(p,q): aux = (p - 1) * (q - 1) return aux
Calculando números primos – Python
Um clássico problema de programação é o calculo para descobrir números primos de forma rápida e precisa. Por isso, decidi fazer no meu tempo ocioso uma função em python que retorne se um número é ou não primo.
Usei o teorema que diz que todo o número não primo é divisivel por outro menor ou igual a sua raiz quadrada e o resultado foi o seguinte:
import math def primo(a): for i in xrange(2,int(math.sqrt(a)+1)): if(a%i==0): print("%d nao e primo" % a) return 0 print("%d e primo" % a) return 1
![[FSF Associate Member]](/getButton.png){kind=small}
Calendário
| S | M | T | W | T | F | S |
|---|---|---|---|---|---|---|
| « Nov | ||||||
| 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 | |||