File Coverage

blib/lib/Math/GF/Zn.pm
Criterion Covered Total %
statement 57 62 91.9
branch 8 14 57.1
condition 1 3 33.3
subroutine 17 19 89.4
pod 13 13 100.0
total 96 111 86.4


line stmt bran cond sub pod time code
1             package Math::GF::Zn;
2 4     4   20 use strict;
  4         7  
  4         89  
3 4     4   13 use warnings;
  4         6  
  4         132  
4             { our $VERSION = '0.004'; }
5              
6 4     4   15 use Scalar::Util qw< blessed >;
  4         6  
  4         218  
7             use overload
8 4         17 '/' => 'divided_by',
9             '==' => 'equal_to',
10             'eq' => 'equal_to',
11             '-' => 'minus',
12             '!=' => 'not_equal_to',
13             '+' => 'plus',
14             '""' => 'stringify',
15             '*' => 'times',
16 4     4   19 '**' => 'to_power';
  4         5  
17              
18 4     4   561 use Ouch;
  4         7  
  4         12  
19 4     4   214 use Moo;
  4         12  
  4         28  
20              
21             has field => (
22             is => 'ro',
23             required => 1,
24             isa => sub {
25             my $F = shift;
26             (blessed($F) && $F->isa('Math::GF'))
27             or ouch 500, 'field is not a valid Math::GF instance';
28             $F->order_is_prime
29             or ouch 500, 'cannot build Zn over non-prime n';
30             return 1;
31             },
32             );
33              
34             # the "n" in "Zn"
35             has n => (
36             is => 'ro',
37             init_arg => undef,
38             lazy => 1,
39             default => sub { shift->field->order },
40             );
41              
42             # the value of this object
43             has v => (
44             is => 'ro',
45             default => 0,
46             );
47              
48             # the multiplicative inverse
49             has i => (
50             is => 'ro',
51             lazy => 1,
52             builder => 'BUILD_multiplicative_inverse',
53             );
54              
55             has o => (
56             is => 'ro',
57             lazy => 1,
58             builder => 'BUILD_additive_inverse',
59             );
60              
61             sub assert_compatibility {
62 1523     1523 1 1840 my ($self, $other) = @_;
63 1523 50 33     5848 (blessed($other) && $other->isa('Math::GF::Zn'))
64             || ouch 500, 'one of the operands is not a Math::GF::Zn object';
65 1523         22150 my $n = $self->n;
66 1523 50       23908 $n == $other->n
67             || ouch 500, 'the two operands are not in the same field';
68 1523         7101 return $n;
69             } ## end sub assert_compatibility
70              
71             sub BUILD_multiplicative_inverse {
72 5     5 1 338 my $self = shift;
73 5 50       12 my $v = $self->v or ouch 500, 'no inverse for 0';
74 5         58 my $n = $self->n;
75 5         23 my ($i, $x) = (1, 0);
76 5         13 for (1 .. $n - 1) {
77 13         16 $x = ($x + $v) % $n;
78 13 100       66 return $_ if $x == 1;
79             }
80 0         0 ouch 500, "no inverse for $v in Z_$n"; # never happens
81             } ## end sub BUILD_multiplicative_inverse
82              
83             sub BUILD_additive_inverse {
84 0     0 1 0 my $self = shift;
85 0         0 return $self->n - $self->v;
86             }
87              
88             sub divided_by {
89 3     3 1 24 my ($self, $other, $swap) = @_;
90 3         6 my $n = $self->assert_compatibility($other);
91 3 50       5 ($self, $other) = ($other, $self) if $swap; # never happens...
92 3         40 return $self->new(
93             field => $self->field,
94             v => (($self->v * $other->i) % $n),
95             );
96             } ## end sub divided_by
97              
98             sub equal_to {
99 641     641 1 11567 my ($self, $other, $swap) = @_;
100 641         982 my $n = $self->assert_compatibility($other);
101 641         1695 return $self->v == $other->v;
102             }
103              
104             sub inv {
105 1     1 1 2 my $self = shift;
106 1         21 return $self->new(
107             field => $self->field,
108             v => $self->i,
109             i => $self->v,
110             );
111             }
112              
113             sub minus {
114 309     309 1 4078 my ($self, $other, $swap) = @_;
115 309         507 my $n = $self->assert_compatibility($other);
116 309         4601 return $self->new(
117             field => $self->field,
118             v => (($self->v - $other->v) % $n),
119             );
120             } ## end sub minus
121              
122             sub not_equal_to {
123 93     93 1 3896 return !shift->equal_to(@_);
124             }
125              
126             sub opp {
127 0     0 1 0 my $self = shift;
128 0         0 return $self->new(
129             field => $self->field,
130             v => $self->o,
131             o => $self->v,
132             );
133             }
134              
135             sub plus {
136 182     182 1 2788 my ($self, $other, $swap) = @_;
137 182         273 my $n = $self->assert_compatibility($other);
138 182         2492 return $self->new(
139             field => $self->field,
140             v => (($self->v + $other->v) % $n),
141             );
142             } ## end sub plus
143              
144             sub stringify {
145 93     93 1 3677 return shift->v;
146             }
147              
148             sub times {
149 388     388 1 7053 my ($self, $other, $swap) = @_;
150 388         593 my $n = $self->assert_compatibility($other);
151 388         5443 return $self->new(
152             field => $self->field,
153             v => (($self->v * $other->v) % $n),
154             );
155             } ## end sub times
156              
157             sub to_power {
158 59     59 1 584 my ($self, $exp, $swap) = @_;
159 59 50       110 ouch 500, 'cannot elevate' if $swap;
160 59         892 my ($n, $v, $x) = ($self->n, $self->v, 1);
161 59         454 while ($exp > 0) {
162 3 50       8 $x = ($x * $v) % $n or last;
163 3         5 $exp--;
164             }
165 59         820 return $self->new(
166             field => $self->field,
167             v => $x,
168             );
169             } ## end sub to_power
170              
171             1;