Algoritmo de Euclides estendido em Perl

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

[ Hits: 3.700 ]

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

FileSystem Alert

Beep-Media-Player for Torsmo

Mega Sena

Randomize MP3

Relatórios do Sarg por grupo


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts