Criptografia Numaboa
Home 
Criptografia Substituição
Criptografia Substituição
Novidades
Plugin de Autenticação para o Joomla 1.5
Como se tratava o estupro em 1833
Adobe Flash Player e Cookies ladrões
Objetos e Manipuladores (handles)
Na Aldeia
3440 registros
0 hoje
0 nesta semana
2 neste mêsEstatística
Artigos: 963Leituras: 5017127
Arquivados: 39
Downloads: 443
Baixados: 182475
Glossário: 1208
Bibliografia: 25
Links: 89
Visitas de onde?
| 89,2% |  | Brasil |
| 8,2% |  | Portugal |
| 0,8% |  | EUA |
| 0,1% |  | Espanha |
| 0,1% |  | Japão |
Visitantes
| Hoje: | 36 |
| Ontem: | 1201 |
| Semana passada: | 13050 |
| Este mês: | 8041 |
| Mês passado: | 70404 |
| Total: | 506890 |
Registro/Login
Usuários registrados têm algumas regalias!
| Algoritmo de Euclides estendido * |
 |
 |
 |
| Escolinha da Aldeia - Ferramentas Matemáticas | |
| Escrito por vovó Vicki | |
| Dom, 17.04.2005 09:49 | |
|
O Algoritmo de Euclides é uma das formas de se encontrar o MDC - máximo divisor comum de dois números inteiros. O MDC é uma combinação linear destes dois números. O Algoritmo de Euclides estendido, ao invés de retornar um valor único, fornece a combinação linear, muito útil quando os inteiros são primos entre si. Por exemplo:
MDC(120,23) = 1
120 e 23 são números inteiros, primos entre si porque não existe um divisor maior
do que 1 que divida ambos.
O Algoritmo de Euclides estendido retorna ax + by = MDC(a, b), ou seja,
120*-9 + 23*47 = MDC(120,23)
Um pouco de álgebra para entender o Algoritmo de Euclides estendidoPara encontrar o MDC(120,23) usando o Algoritmo de Euclides, procede-se da seguinte forma:
(1) 120/23 = 5 resta 5
(2) 23/5 = 4 resta 3
(3) 5/3 = 1 resta 2
(4) 3/2 = 1 resta 1
2/1 = 2 resta 0
MDC(120,23) = 1
Levando-se em conta apenas os restos encontrados, pode-se dizer que:
(1) 5 = 1*120 - 5*23
(2) 3 = 1*23 - 4*5 ................ e, como 5 = 1*120 - 5*23
3 = 1*23 - 4(1*120 - 5*23)
3 = -4*120 + 21*23
(3) 2 = 1*5 - 1*3 ................. como 5 = 1*120 - 5*23 e
3 = -4*120 + 21*23
2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
2 = 5*120 - 26*23
(4) 1 = 1*3 - 1*2
1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
1 = -9*120 + 47*23
portanto, x = -9 e y = 47 e -9*120 + 47*23 = MDC(120,23)
Cálculo do Algoritmo de Euclides estendido(apenas para inteiros positivos!)
 |
|
| Atualização Sex, 08.02.2008 19:58 |
Esta ferramenta é muito útil nas nossas lidas criptológicas!
vovó Vicki
Esta página já foi vista 11732 vezes na Aldeia Numaboa © 1998-2009
Exceto onde especificamente citado, todo material deste site está sob Licença Creative Commons
Dica: tudo aqui na Aldeia é melhor visto com os olhos abertos, no Firefox e na resolução 1024x768
Exceto onde especificamente citado, todo material deste site está sob Licença Creative Commons
Dica: tudo aqui na Aldeia é melhor visto com os olhos abertos, no Firefox e na resolução 1024x768
Comentários
:hmmm: O algoritmo de Euclides é 100% eficiente?
gostei!!!
e massa :tchau: :wub: :meudeus: :happy: :huh: :morto: :medo: :amor: :bravo: :negativo:
1 2