Algoritmo de Euclides estendido em Perl
Para economizar explicações, relembrando criptografia de chave assimétrica com este artigo: http://www.vivaolinux.com.br/artigo/Criptografia-assimetrica-com-o-RSA?pagina=4 bem na página que mais interessa neste momento.
Parte do problema consiste em:
"Dado dois números inteiros positivos E e N, encontre um terceiro inteiro positivo D de tal modo que E vezes D quando dividido por N dê resto 1."
É a proposta desse código.
Parte do problema consiste em:
"Dado dois números inteiros positivos E e N, encontre um terceiro inteiro positivo D de tal modo que E vezes D quando dividido por N dê resto 1."
É a proposta desse código.
Descrição
Para economizar explicações, relembrando criptografia de chave assimétrica com este artigo: http://www.vivaolinux.com.br/artigo/Criptografia-assimetrica-com-o-RSA?pagina=4 bem na página que mais interessa neste momento.
Parte do problema consiste em:
"Dado dois números inteiros positivos E e N, encontre um terceiro inteiro positivo D de tal modo que E vezes D quando dividido por N dê resto 1."
É a proposta desse código.
Parte do problema consiste em:
"Dado dois números inteiros positivos E e N, encontre um terceiro inteiro positivo D de tal modo que E vezes D quando dividido por N dê resto 1."
É a proposta desse código.
#!/usr/bin/perl
=pod
0 1
101 29 3 1 0
29 14 2 -3 1
14 1 14 7 -2
dispensa calculo da segunda coluna
=cut
use warnings;
use strict;
sub gcd_ext {
my @n=(0, shift, shift);
my @d1=(1, 0);
# my @d2=(0, 1);
my @q = (0);
while ($n[-1]!=0) {
push (@n,$n[-2]%$n[-1]);
push (@q,($n[-3]-$n[-1])/$n[-2]);
push (@d1,$d1[-2]-$q[-1]*$d1[-1]);
# push (@d2,$d2[-2]-$q[-1]*$d2[-1]);
}
return ($d1[-2]<0?$n[2]+$d1[-2]:$d1[-2]);
}
my $x = 29;
my $y = 101;
my $z = gcd_ext($x,$y);
print "$x * x = 1 (mod $y)\n";
print "$x . $z dividido por $y tem resto 1.\n"