[ create a new paste ] login | about

Link: http://codepad.org/cjERZy1r    [ raw code | output | fork ]

Perl, pasted on Mar 3:
#findP takes a number n and return the smallest divisor of n
sub findP{
	my ($n) = @_;
	return 2 if ($n%2 == 0);
	# try to divide n by all the odd numbers i less than sqrt of n, return i if the division reminder = 0
	for (my $i = 3; $i<sqrt($n); $i = $i+2){
		return $i if ($n%$i == 0);
	}
}


# find the inverse of e mod phiN using extended euclidian algorithm
# I got some help from http://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/ 
sub modularInverse {
	my ($e, $phiN) = @_;
	my $dt = 1;
	my $d = 0;
	my $div, $r, $m, $n;
	while($e != 0) {
		$div = int($phiN / $e);
		$r = $phiN % $e;
		$m = $d - $div * $dt;
		$d = $dt;
		$dt = $m; 
		$phiN = $e;
		$e = $r;
	}
	#phiN = 1 if the gcd of phiN and e = 1, return 0 if phiN and e are not relatively prime otherwise, return d
	return $d if($phiN == 1);
	return 0;
}

#calculate x^c mod n using modular exponentation algorithm
sub modExp{
	my ($x, $c ,$n) = @_;
	my $str = unpack("B32", pack("N", $c)); #convert c to binary
    $str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
	my @b = split (//, $str); 
	my $z = 1;
	foreach $bb(@b){
		$z = ($z*$z)%$n;
		$z = ($z * $x)%$n if ($bb ==1);
	}
	return $z;
}

#find the correspnding 3 letter word correspnding to number $nnn
sub word{
	my ($nnn) = @_;
	foreach my $x(0..25){
		foreach my $y(0..25){
			foreach my $z (0..25){
				if (($x * 26 * 26 + $y * 26 + $z) == $nnn){
					printf '%c', $x+65 ;
					printf '%c', $y + 65;
					printf '%c', $z + 65 ;
					print " ";
					return;
				}
					
			}
		}
	}
}


my $n = 88579;
my $e = 48925;

my $p = findP($n);
my $q = $n/$p;
my $phiN = ($p-1)*($q-1);
print "p = $p \nq = $q \nphiN = $phiN\n";
$d = modularInverse($e, $phiN);
print $d + "....\n";
if ($d == 0){
	print("$e and phiN are not relatively prime");
	exit;
}
print "d = $d\n";
while (my $in = <DATA> ) { 
    chomp($in);            
    my @m = split " ",$in;
    
    foreach my $nnn (@m) {
		$temp = modExp($nnn,$d,$n);
		word($temp);
    }print "\n";
}

__END__
70938 53671 25410 5651 53215 15386 65574 65920 19935 78250 26540 64323
58815 5513 38297 8951 10611 3323 18479 15458 65574 47974 12405 75177
36321 48681 73681 38194 26700 757 74170 40781 70016 65963 69373 44208
3136 77179 38052 6165 58552 51981 8362 40116 78250 15607 41359 66124
52270 12405 27874 52231 45962 12667 20541 51850 12405 27624 66245 4997
60656 47193 24012 53671 57131 67298 38623 40206 14086 10614 6085 60041
74158 9367 49093 70518 35180 24901 59239 73233 34064 75898 39394 61692
21940 48177 58225 15179 66622 46680 60400 53787 10455 38838 19379 50904
31168 12389 27834 26901 54593 76332 47449 59597 40921 70446 19810 1386
57009 60408 30022 25410 266 25667 26992 32209 1222 34044 52231 2340
15802 39372 19993 40921 52066 59616 76541 4534 23569 17300 74170 52675
32011 65171 256 6335 14951 74399 4987 12405 61311 75944 27099 78646
63488 2468 35123 52369 68432 24075 47376 22035 41462 68903 41519 27641
41519 10455 59597 23569 6085 17300 21917 42546 8396 52526 17612 56683
70237 32713 42198 42381 70760 39167 64375 71322 15944 17206 26461 56290
32699 9023 43936 46376 47209 76049 63544 5168 16439 21309 55116 76332
12389 51765 23569 72587 77532 37995 51661 2112 73047 22630 74456 47449
49734 76332 47449 77988 3647 63065 70938 53671 25410 21313 18578 16681
70069 44915 51168 73501 35108 39600 35250 77529 10849 66622 23988 76332
32011 13760 75334 22630
	


Output:
p = 283 
q = 313 
phiN = 87984
-18683d = -18683
KDA NOP HCU RIV 
NNF 
JTF CGF BPK 

KQW TMZ XYQ 
KAP DJF 

IPE MNL 
PYO 
YBZ ULW 
MQM QWT BPK 
HPZ GBS UAV XKD RXJ 
DZF MTG QIQ SQZ 
MNL QWT LZI ECF 
BKN PER BKP 
HTH PUL CRE 
ELO ACG 
NPC KDA 
LIN SEJ COL 
HPZ 



Create a new paste based on this one


Comments: