Permalink
Browse files

Merge remote-tracking branch 'bubaflub/fix_aks' into fix_aks

Conflicts:
	lib/Math/Primality/BigPolynomial.pm
  • Loading branch information...
2 parents c546f2c + 00bce30 commit 8a5aca4958fa7488d5ab5664a996a67ef80cf8e3 @leto committed Sep 26, 2012
Showing with 34 additions and 33 deletions.
  1. +8 −9 lib/Math/Primality/AKS.pm
  2. +24 −23 lib/Math/Primality/BigPolynomial.pm
  3. +2 −1 t/big_polynomial.t
View
@@ -114,12 +114,12 @@ sub is_aks_prime($) {
my $final_size = Math::GMPz->new(0);
Rmpz_mod($final_size, $n, $r);
my $compare = Math::Primality::BigPolynomial->new(Rmpz_get_ui($final_size));
- $compare->setCoef(1, Rmpz_get_ui($final_size));
- $compare->setCoef($a, 0);
+ $compare->setCoef(Math::GMPz->new(1), $final_size);
+ $compare->setCoef(Math::GMPz->new($a), 0);
my $res = Math::Primality::BigPolynomial->new($intr);
my $base = Math::Primality::BigPolynomial->new(1);
- $base->setCoef($a, 0);
- $base->setCoef(1, 1);
+ $base->setCoef(Math::GMPz->new(0), $a);
+ $base->setCoef(Math::GMPz->new(1), 1);
Math::Primality::BigPolynomial::mpz_poly_mod_power($res, $base, $n, $n, $intr);
@@ -139,11 +139,10 @@ Jonathan "Duke" Leto C<< <jonathan@leto.net> >>
=head1 BUGS
-Please report any bugs or feature requests to C<bug-math-primality-aks at rt.cpan.org>,
-or through the web interface at
-L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math::Primality::AKS>. I will be
-notified, and then you'll automatically be notified of progress on your bug as I
-make changes.
+Please report any bugs or feature requests to
+C<bug-math-primality-aks at rt.cpan.org>, or through the web interface at
+L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math::Primality::AKS>.
+I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
=head1 THANKS
@@ -9,21 +9,24 @@ sub new {
my $class = shift;
my $construction_junk = shift;
if ($construction_junk) {
- if ( ref($construction_junk) eq 'ARRAY' ) {
+ my $type = ref $construction_junk;
+ if ( $type eq 'ARRAY' ) {
$self->{COEF} = $construction_junk;
- $self->{DEGREE} = scalar(@$construction_junk);
+ } elsif ( $type eq 'Math::Primality::BigPolynomial') {
+ foreach my $coef (@{$construction_junk->{COEF}}) {
+ my $temp = Rmpz_init_set($coef);
+ push @{$self->{COEF}}, $temp;
+ }
} else {
- $self->{DEGREE} = $construction_junk;
- my @a = [];
+ my $a = [];
for ( my $i = 0 ; $i < $construction_junk ; $i++ ) {
- push @a, Math::GMPz->new(0);
+ push @$a, Math::GMPz->new(0);
}
- $self->{COEF} = \@a;
+ $self->{COEF} = $a;
}
}
else {
$self->{COEF} = [ Math::GMPz->new(0) ];
- $self->{DEGREE} = 1;
}
bless( $self, $class );
return $self;
@@ -37,18 +40,17 @@ sub coef {
sub degree {
my $self = shift;
- if (@_) { $self->{DEGREE} = shift }
- return $self->{DEGREE};
+ return (scalar @{$self->{COEF}} - 1);
}
sub getCoef {
my $self = shift;
my $i = shift;
if ( $i > $self->degree() ) {
- return 0;
+ return Math::GMPz->new(0);
}
return undef if $i < 0;
- return ${ $self->{COEF} }[$i];
+ return $self->{COEF}->[$i];
}
sub isEqual {
@@ -74,41 +76,40 @@ sub setCoef {
}
if ( $index > $self->degree() ) {
- for ( my $j = $self->degree() + 1 ; $j <= $index ; $j++ ) {
+ for ( my $j = $self->degree() + 1 ; $j < $index ; $j++ ) {
push @{ $self->{COEF} }, Math::GMPz->new(0);
}
- push @{ $self->{COEF} }, $new_coef;
+ $self->{COEF}->[$index] = $new_coef;
$self->degree($index);
}
else {
- ${ $self->{COEF} }[$index] = $new_coef;
+ $self->{COEF}->[$index] = $new_coef;
}
}
sub compact {
my $self = shift;
my $i = 0;
- LOOP: for ( $i = $self->degree() - 1 ; $i > 0 ; $i-- ) {
+ LOOP: for ( $i = $self->degree(); $i > 0 ; $i-- ) {
if ( Math::GMPz::Rmpz_cmp_ui( $self->getCoef($i), 0 ) != 0 ) {
last LOOP;
}
pop @{ $self->{COEF} };
}
if ( $i != $self->degree() ) {
- $self->degree( $i + 1 );
+ $self->degree( $i );
}
}
sub clear {
my $self = shift;
- $self->{COEF} = undef;
- $self->{DEGREE} = undef;
$self->{COEF} = [ Math::GMPz->new(0) ];
- $self->{DEGREE} = 1;
}
sub mpz_poly_mod_mult {
- my ( $rop, $x, $y, $mod, $polymod ) = @_;
+ my ( $rop, $copy_x, $copy_y, $mod, $polymod ) = @_;
+ my $x = Math::Primality::BigPolynomial->new($copy_x);
+ my $y = Math::Primality::BigPolynomial->new($copy_y);
die "mpz_poly_mod_mult: polymod must be defined!" unless $polymod;
@@ -122,8 +123,8 @@ sub mpz_poly_mod_mult {
my $sum = Math::GMPz->new(0);
my $temp = Math::GMPz->new(0);
for ( my $j = 0 ; $j <= $i ; $j++ ) {
- Rmpz_add($temp, $temp,
- $y->getCoef( $i - $j ) + $y->getCoef( $i + $polymod - $j ) );
+ Rmpz_add($temp, $y->getCoef( $i - $j ),
+ $y->getCoef( $i + $polymod - $j ) );
Rmpz_mul( $temp, $x->getCoef($j), $temp );
Rmpz_add( $sum, $sum, $temp );
}
@@ -159,7 +160,7 @@ sub mpz_poly_mod_power {
mpz_poly_mod_mult( $rop, $rop, $rop, $mult_mod, $poly_mod );
if ( Rmpz_tstbit( $power, $i ) ) {
- mpz_poly_mod_mul( $rop, $rop, $x, $mult_mod, $poly_mod );
+ mpz_poly_mod_mult( $rop, $rop, $x, $mult_mod, $poly_mod );
}
if ( $i == 0 ) {
View
@@ -18,7 +18,8 @@ isa_ok($b, 'Math::Primality::BigPolynomial');
is($b->getCoef(0), 1, 'coef(0) is 1');
is($b->getCoef(1), 3, 'coef(1) is 3');
is($b->getCoef(2), 7, 'coef(2) is 7');
-is($b->getCoef(3), undef, 'coef(3) is undef');
+# this is a bit wonky
+cmp_ok($b->getCoef(3),'==', Math::GMPz->new(0), 'coef(3) is 0');
is($b->getCoef(-1), undef, 'coef(-1) is undef');
is($b->getCoef(-10), undef, 'coef(-10) is undef');

0 comments on commit 8a5aca4

Please sign in to comment.