Algoritmo de Euclides estendido em Perl

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

[ Hits: 3.193 ]

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

Mega Sena

Screenshot

Role-Playing Script

MoOnCrack

fonte.pl


  

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