Algoritmo de Euclides estendido em Perl

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

[ Hits: 3.249 ]

Download gcd_ext-001.pl




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

Beep-Media-Player for Torsmo

Wallpaper no Fluxbox

Diminuir ou aumentar o brilho de notebook

Login AUDIT

Randomize MP3


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts