Skip Menu |

This queue is for tickets about the Math-BigInt CPAN distribution.

Report information
The Basics
Id: 62918
Status: resolved
Priority: 0/
Queue: Math-BigInt
People
Owner: Nobody in particular
Requestors: peter.john.acklam [...] gmail.com
Cc:
AdminCc:
Bug Information
Severity: Normal
Broken in:
  • 1.70
  • 1.71
  • 1.72
  • 1.73
  • 1.74
  • 1.75
  • 1.76
  • 1.77
  • 1.78
  • 1.79
  • 1.80
  • 1.82
  • 1.83
  • 1.84
  • 1.85
  • 1.86
  • 1.87
  • 1.88
  • 1.89
  • 1.90
  • 1.91
  • 1.92
  • 1.93
  • 1.94-TRIAL
  • 1.95
  • 1.96
  • 1.97
  • 1.98
Fixed in: (no value)

History Show all quoted text
  Thu Nov 11 05:00:44 2010 peter.john.acklam [...] gmail.com - Ticket created
Subject: _modpow(x, y, z) returns 1, not 0, when x = 0 and y > 0
Mathematically, 0^a (mod b) = 0, when a and b are positive integers. The Math::BigInt::Calc library returns 1, not 0. Here is a code snipped that prints 1, not 0, as it should: ---------------------------------------- use strict; use warnings; use Math::BigInt::Calc; my $CALC = 'Math::BigInt::Calc'; my $x = $CALC -> _new(0); my $y = $CALC -> _new(5); my $z = $CALC -> _new(3); my $ans = $CALC -> _modpow($x, $y, $z); # ($x ** $y) % $z print $CALC -> _str($ans), "\n"; ----------------------------------------
  Thu Nov 11 13:01:48 2010 jonathan [...] leto.net - Correspondence added
Subject: Re: [rt.cpan.org #62918] _modpow(x, y, z) returns 1, not 0, when x = 0 and y > 0
Date: Thu, 11 Nov 2010 07:09:19 -0800
To: bug-Math-BigInt [...] rt.cpan.org
From: Jonathan Leto <jonathan [...] leto.net>
Howdy, Show quoted text
>     Subject: _modpow(x, y, z) returns 1, not 0, when x = 0 and y > 0
[snip] Show quoted text
> Mathematically, > >  0^a (mod b) = 0, when a and b are positive integers.
This is correct, and is actually true for all a, b != 0. Show quoted text
> > The Math::BigInt::Calc library returns 1, not 0. Here is a code snipped > that prints 1, not 0, as it should: > > ---------------------------------------- > use strict; > use warnings; > use Math::BigInt::Calc; > > my $CALC = 'Math::BigInt::Calc'; > > my $x = $CALC -> _new(0); > my $y = $CALC -> _new(5); > my $z = $CALC -> _new(3); > > my $ans = $CALC -> _modpow($x, $y, $z);   # ($x ** $y) % $z
I think your above comment is wrong, which is confusing, it should be: # $x ** ( $y % $z ) Show quoted text
> print $CALC -> _str($ans), "\n"; > ---------------------------------------- >
I think this is a valid bug. If you could turn this code into a failing test, that would be really useful. Duke -- Jonathan "Duke" Leto jonathan@leto.net http://leto.net
  Thu Nov 11 13:01:49 2010 The RT System itself - Status changed from 'new' to 'open'
  Thu Nov 11 16:26:13 2010 peter.john.acklam [...] gmail.com - Correspondence added
On Thu Nov 11 13:01:48 2010, LETO wrote: Show quoted text
>
> > Mathematically, > > > >  0^a (mod b) = 0, when a and b are positive integers.
> > This is correct, and is actually true for all a, b != 0.
Yes, but Math::BigInt::Calc only deals with non-negative integers. The stuff for negative a and b is taken care of in Math::BigInt->bmodpow() front-end. Show quoted text
> > my $ans = $CALC -> _modpow($x, $y, $z);   # ($x ** $y) % $z
> > I think your above comment is wrong, which is confusing, it should be: > > # $x ** ( $y % $z )
The documentation in Math::BigInt says ($num**$exp) % $mod), a comment in the source of Math::BigInt::Calc says # modulus of power ($x ** $y) % $z, and if you google "modular exponentiation", I think you will see that this is the most common definition. Personally, I haven't seen any other definition than this, but that doesn't mean no-one uses it. Show quoted text
> I think this is a valid bug. If you could turn this code into a > failing test, that would be really useful.
I have fixed the code and added test cases. Florian will receive a Github pull request some day soon.
  Mon Nov 15 03:16:24 2010 rafl [...] debian.org - Status changed from 'open' to 'resolved'