Algoritmo de Euclides estendido em Perl [Perl]

Algoritmo de Euclides estendido em Perl

Publicado por Perfil removido (última atualização em 12/04/2013)

[ Hits: 3.955 ]

Download gcd_ext-001.pl

1 0

Denuncie Favoritos Indicar

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.

Esconder código-fonte

#!/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"

Scripts recomendados

Comentários

Nenhum comentário foi encontrado.