raku excursion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# subset Composite of Int where {!.is-prime}; | |
# subset Prime of Int where {.is-prime}; | |
use Math::Vector; | |
class ZModInt {...} | |
# extended GCD. | |
sub egcd(Int:D $a, Int:D $b --> List:D) { | |
return ($a,1,0) unless $b; | |
my ($s,$r) = 0,$b; | |
my ($prev_s,$prev_r) = 1,$a; | |
while $r { | |
my $q = $prev_r div $r; | |
($prev_r, $r) = $r, $prev_r - $q * $r; | |
($prev_s, $s) = $s, $prev_s - $q * $s; | |
} | |
($prev_r, $prev_s, ($prev_r - $prev_s * $a) div $b) | |
} | |
sub invmod(Int:D $a, Int:D $m --> Int:D) { | |
# Probably better to just do expmod(m, -1)? (TODO: time it) | |
my $β = egcd($a,$m)[1]; | |
$β += $m if $β < 0; | |
$β | |
} | |
sub get-prime(Range $r) { | |
loop { | |
my $p = $r.roll; | |
return $p if $p.is-prime; | |
} | |
} | |
class ZMod { | |
has Int $.modulus; | |
method CALL-ME(Int:D $z) { | |
ZModInt.new: self, $z % $!modulus | |
} | |
method inverse(Int:D $z) { | |
ZModInt.new: self, invmod($z, $!modulus) | |
} | |
} | |
class ZModInt is Int { | |
has ZMod $.parent; | |
multi method new(ZMod $parent, Int $value) { | |
my $what = callwith($value); | |
$what.BUILD($parent); | |
return $what; | |
} | |
submethod BUILD(ZMod $zm) { | |
$!parent = $zm; | |
} | |
} | |
&infix:<+>.wrap: sub (\a, \b) { | |
return a.parent.(Int.new(a) + Int.new(b)) if a ~~ ZModInt; | |
return b.parent.(a + Int.new(b)) if b ~~ ZModInt; | |
callsame | |
} | |
&infix:<->.wrap: sub (\a, \b) { | |
return a.parent.(Int.new(a) - Int.new(b)) if a ~~ ZModInt; | |
return b.parent.(a - Int.new(b)) if b ~~ ZModInt; | |
callsame | |
} | |
&infix:<*>.wrap: sub (\a, \b) { | |
return a.parent.(Int.new(a) * Int.new(b)) if a ~~ ZModInt; | |
return b.parent.(a * Int.new(b)) if b ~~ ZModInt; | |
callsame | |
} | |
&infix:</>.wrap: sub (\a, \b) { | |
return a * a.parent.inverse(b) if a ~~ ZModInt; | |
return a * b.parent.inverse(b) if b ~~ ZModInt; | |
callsame | |
} | |
&infix:<**>.wrap: sub (\a, \e) { | |
ZModInt.new(a.parent, | |
Int.new(a).expmod(e, a.parent.modulus)) if a ~~ ZModInt; | |
callsame | |
} | |
# multi sub infix:<+>(ZModInt $a, Int $b) is default { | |
# $a.parent.(Int.new($a) + $b) | |
# } | |
# multi sub infix:<+>(Int $a, ZModInt $b) { | |
# $b.parent.($a + Int.new($b)) | |
# } | |
# multi sub infix:<->(ZModInt $a, Int $b) is default { | |
# $a.parent.(Int.new($a) - $b) | |
# } | |
# multi sub infix:<->(Int $a, ZModInt $b) { | |
# $b.parent.($a - Int.new($b)) | |
# } | |
# multi sub infix:<*>(ZModInt $a, Int $b) is default { | |
# $a.parent.(Int.new($a) * $b) | |
# } | |
# multi sub infix:<*>(Int $a, ZModInt $b) { | |
# $b.parent.($a * Int.new($b)) | |
# } | |
# multi sub infix:</>(ZModInt $a, Int $b) is default { | |
# $a * $a.parent.inverse($b) | |
# } | |
# multi sub infix:</>(Int $a, ZModInt $b) { | |
# $a * $b.parent.inverse($b) | |
# } | |
multi sub prefix:<->(ZModInt:D $a --> ZModInt:D) { | |
ZModInt.new: $a.parent, $a.parent.modulus - Int.new($a) | |
} | |
multi sub prefix:<+>(ZModInt:D $a --> ZModInt:D) { | |
if $a > $a.parent.modulus div 2 { | |
ZModInt.new: $a.parent, Int.new($a) - $a.parent.modulus | |
} else { $a } | |
} | |
multi sub infix:<**>(ZModInt:D $a, Int:D $e --> ZModInt:D) { | |
ZModInt.new: $a.parent, Int.new($a).expmod($e, $a.parent.modulus) | |
} | |
# Make a random small finite field. | |
my $F = ZMod.new(modulus=>get-prime(2**7 .. 2**8)); | |
# Some elements of this finite field. | |
my $a = $F(50); | |
my $b = $F(11); | |
"$a ** 2 = {$a**2} (mod {$F.modulus})".say; | |
"$b - $a = {$b-$a} (mod {$F.modulus})".say; | |
my $arr1 = (1..4).map(* * $a); | |
my $arr2 = (1..4).map($b ** *); | |
"<$arr1> + <$arr2> = <{$arr1 »+« $arr2}> (mod {$F.modulus})".say; | |
my $vec1 = Math::Vector($arr1); | |
my $vec2 = Math::Vector($arr2); | |
"$vec1 + $vec2 = vs<{$vec1.coordinates »+« $vec2.coordinates}> (mod {$F.modulus})".say; | |
"$vec1 + $vec2 = {$vec1 + $vec2} (mod {$F.modulus}) <--- ????".say; | |
repl |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment