[Gmp-commit] /home/hgfiles/gmp: Comment on residue class representation Mod B...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/7b74eca1c4b6
changeset: 13080:7b74eca1c4b6
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Dec 15 17:03:30 2009 +0100
description:
Comment on residue class representation Mod B^n-1.

diffstat:

 ChangeLog                 |   1 +
 mpn/generic/mulmod_bnm1.c |  10 ++++++++++
 2 files changed, 11 insertions(+), 0 deletions(-)

diffs (31 lines):

diff -r 51db7a0f4774 -r 7b74eca1c4b6 ChangeLog
--- a/ChangeLog	Tue Dec 15 13:34:59 2009 +0100
+++ b/ChangeLog	Tue Dec 15 17:03:30 2009 +0100
@@ -1,6 +1,7 @@
 2009-12-15  Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* gmp-impl.h (mpn_ni_invertappr): Added prototype and name-mangling.
+	* mpn/generic/mulmod_bnm1.c: Comment representation of class [0].
 
 2009-12-14  Niels Möller  <nisse at lysator.liu.se>
 
diff -r 51db7a0f4774 -r 7b74eca1c4b6 mpn/generic/mulmod_bnm1.c
--- a/mpn/generic/mulmod_bnm1.c	Tue Dec 15 13:34:59 2009 +0100
+++ b/mpn/generic/mulmod_bnm1.c	Tue Dec 15 17:03:30 2009 +0100
@@ -70,6 +70,16 @@
 
 
 /* Computes {rp,rn} <- {ap,an}*{bp,bn} Mod(B^rn-1)
+ *
+ * The result is expected to be ZERO if and only if one of the operand
+ * already is. Otherwise the class [0] Mod(B^rn-1) is represented by
+ * B^rn-1. This should not be a problem if mulmod_bnm1 is used to
+ * combine results and obtain a natural number when one knows in
+ * advance that the final value is less than (B^rn-1).
+ * Moreover it should not be a problem if mulmod_bnm1 is used to
+ * compute the full product with an+bn <= rn, because this condition
+ * implies (B^an-1)(B^bn-1) < (B^rn-1) .
+ *
  * Requires both 0 < bn <= an <= rn
  * Scratch need: rn + 2 + (need for recursive call OR rn + 2). This gives
  *