#!/usr/bin/perl

use bignum;

use warnings;
use strict;

my @ps = ( 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43);

my $m = 2;
my $p = 17;
my $q = 19;
my $n = $p*$q;

#bindump();
my $e;
if (0) {
	my @res;
	$e = 1;
	my $y = $m;
	push @res, $y;
	until ($y == 1 or $y == 0 or $e > $n) {
		$y = $y * $m % $n;
		push @res, $y;
		$e++;
	}
	print "$m ** $e % $n = 1\n"; # . join(" ", @res) . "\n";

	print sprintf("%b",$n) . " " . sprintf("%b", ($m**$e - 1)/$n) . "\n\n";
}

my $a = $n;
my $k = 0;
my $x = 1;
while ($a > $m**$k) {
	my $bit = int($a / $m**$k) % $m;

	unless ($bit) {
		$x += $m**$k;
		$a += $m**$k * $n;
	}

#	print "$bit " . sprintf("%b", $a) . " " . sprintf("%b", $x) . "\n";
	$k++;
}
print "\n$m**$k - 1 = $n*$x = $a\n\n";

print "$m**$k % $n = " . $m**$k % $n . "\n\n";

sub bindump {
	foreach my $i (0..$#ps-1) {
		foreach my $j ($i+1..$#ps) {
			my $n = $ps[$i]*$ps[$j];

			my @res;
			my $e = 1;
			my $y = $m;
			push @res, $y;
			until ($y == 1 or $y == 0 or $e > $n) {
				$y = $y * $m % $n;
				push @res, $y;
				$e++;
			}
			print "$m ** $e % $n = 1\n"; # . join(" ", @res) . "\n";

			print sprintf("%b",$n) . " " . sprintf("%b", ($m**$e - 1)/$n) . "\n\n";
		}
	}
}

1;