X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/a22bbdf6fa8e43546da6b4d7f6b0e014cb8deb6c..f52f2db067dc1388b16ab00ddb53e26a381a6e3e:/bbs-jump.c

diff --git a/bbs-jump.c b/bbs-jump.c
index 428915d..7275bd9 100644
--- a/bbs-jump.c
+++ b/bbs-jump.c
@@ -1,13 +1,13 @@
 /* -*-c-*-
  *
- * $Id: bbs-jump.c,v 1.4 2000/07/01 11:20:36 mdw Exp $
+ * $Id$
  *
  * Jumping around a BBS sequence
  *
  * (c) 1999 Straylight/Edgeware
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * This file is part of Catacomb.
  *
@@ -15,35 +15,18 @@
  * it under the terms of the GNU Library General Public License as
  * published by the Free Software Foundation; either version 2 of the
  * License, or (at your option) any later version.
- * 
+ *
  * Catacomb is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Library General Public License for more details.
- * 
+ *
  * You should have received a copy of the GNU Library General Public
  * License along with Catacomb; if not, write to the Free
  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: bbs-jump.c,v $
- * Revision 1.4  2000/07/01 11:20:36  mdw
- * Remove bad type name `bbs_param'.
- *
- * Revision 1.3  2000/06/17 10:44:17  mdw
- * Typesetting fix.
- *
- * Revision 1.2  1999/12/22 15:52:08  mdw
- * Rename `bbs_params' to `bbs_param' for consistency.
- *
- * Revision 1.1  1999/12/10 23:14:59  mdw
- * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "bbs.h"
@@ -57,8 +40,8 @@
 /* --- @jump@ --- *
  *
  * Arguments:	@bbs *b@ = pointer to BBS generator context
- *		@bbs_priv *bp@ = pointer to BBS modulus factors
- *		@unsigned long n@ = number of steps to move
+ *		@const bbs_priv *bp@ = pointer to BBS modulus factors
+ *		@mp *n@ = number of steps to move
  *		@mp *px@ = exponent mod @p@ for a one-step jump
  *		@mp *qx@ = exponent mod @q@ for a one-step jump
  *
@@ -95,7 +78,7 @@
  *		%$p \equiv 3 \pmod 4$%.)
  */
 
-static void jump(bbs *b, bbs_priv *bp, unsigned long n,
+static void jump(bbs *b, const bbs_priv *bp, mp *n,
 		 mp *px, mp *qx)
 {
   mp *ep, *eq;
@@ -106,24 +89,21 @@ static void jump(bbs *b, bbs_priv *bp, unsigned long n,
   {
     mpbarrett mb;
     mp *m;
-    mp *e;
 
-    e = mp_fromulong(MP_NEW, n);
     m = mp_sub(MP_NEW, bp->p, MP_ONE);
     mpbarrett_create(&mb, m);
-    ep = mpbarrett_exp(&mb, MP_NEW, px, e);
+    ep = mpbarrett_exp(&mb, MP_NEW, px, n);
     mpbarrett_destroy(&mb);
     if (qx == px)
       eq = MP_COPY(ep);
     else {
       m = mp_sub(m, bp->q, MP_ONE);
       mpbarrett_create(&mb, m);
-      eq = mpbarrett_exp(&mb, MP_NEW, qx, e);
+      eq = mpbarrett_exp(&mb, MP_NEW, qx, n);
       mpbarrett_destroy(&mb);
     }
 
     mp_drop(m);
-    mp_drop(e);
   }
 
   /* --- Now calculate the residues of @x@ --- */
@@ -172,38 +152,25 @@ static void jump(bbs *b, bbs_priv *bp, unsigned long n,
   b->b = b->k;
 }
 
-/* --- @bbs_ff@ --- *
+/* --- @bbs_{ff,rew}{,n}@ --- *
  *
  * Arguments:	@bbs *b@ = pointer to a BBS generator state
- *		@bbs_priv *bp@ = pointer to BBS modulus factors
- *		@unsigned long n@ = number of steps to make
+ *		@const bbs_priv *bp@ = pointer to BBS modulus factors
+ *		@mp *n@, @unsigned long n@ = number of steps to make
  *
  * Returns:	---
  *
- * Use:		`Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
- *		Requires the factorization of the Blum modulus to do this
- *		efficiently.
+ * Use:		`Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@
+ *		steps.  The @...n@ versions take an @unsigned long@ argument;
+ *		the non-@...n@ versions a multiprecision integer.  If @n@ is
+ *		negative then the generator is stepped in the reverse
+ *		direction.
  */
 
-void bbs_ff(bbs *b, bbs_priv *bp, unsigned long n)
-{
-  jump(b, bp, n, MP_TWO, MP_TWO);
-}
-
-/* --- @bbs_rew@ --- *
- *
- * Arguments:	@bbs *b@ = pointer to a BBS generator state
- *		@bbs_priv *bp@ = pointer to BBS modulus factors
- *		@unsigned long n@ = number of steps to make
- *
- * Returns:	---
- *
- * Use:		`Rewinds' a Blum-Blum-Shub generator by @n@ steps.
- *		Requires the factorization of the Blum modulus to do this
- *		at all.
- */
+static void ff(bbs *b, const bbs_priv *bp, mp *n)
+  { jump(b, bp, n, MP_TWO, MP_TWO); }
 
-void bbs_rew(bbs *b, bbs_priv *bp, unsigned long n)
+static void rew(bbs *b, const bbs_priv *bp, mp *n)
 {
   mp *px = mp_lsr(MP_NEW, bp->p, 2);
   mp *qx = mp_lsr(MP_NEW, bp->q, 2);
@@ -214,6 +181,34 @@ void bbs_rew(bbs *b, bbs_priv *bp, unsigned long n)
   mp_drop(qx);
 }
 
+void bbs_ff(bbs *b, const bbs_priv *bp, mp *n)
+{
+  if (!MP_NEGP(n))
+    ff(b, bp, n);
+  else {
+    n = mp_neg(MP_NEW, n);
+    rew(b, bp, n);
+    mp_drop(n);
+  }
+}
+
+void bbs_ffn(bbs *b, const bbs_priv *bp, unsigned long n)
+  { mp *nn = mp_fromulong(MP_NEW, n); ff(b, bp, nn); mp_drop(nn); }
+
+void bbs_rew(bbs *b, const bbs_priv *bp, mp *n)
+{
+  if (!MP_NEGP(n))
+    rew(b, bp, n);
+  else {
+    n = mp_neg(MP_NEW, n);
+    ff(b, bp, n);
+    mp_drop(n);
+  }
+}
+
+void bbs_rewn(bbs *b, const bbs_priv *bp, unsigned long n)
+  { mp *nn = mp_fromulong(MP_NEW, n); bbs_rew(b, bp, nn); mp_drop(nn); }
+
 /*----- Test rig ----------------------------------------------------------*/
 
 #ifdef TEST_RIG
@@ -243,7 +238,7 @@ static int verify(dstr *v)
   q = bbs_bits(&b, 32);
   bbs_wrap(&b);
 
-  bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k);
+  bbs_rewn(&b, &bp, n + (32 + b.k - 1) / b.k);
   r = bbs_bits(&b, 32);
 
   if (r != p) {
@@ -259,7 +254,7 @@ static int verify(dstr *v)
   }
 
   bbs_seed(&b, x);
-  bbs_ff(&b, &bp, n);
+  bbs_ffn(&b, &bp, n);
   r = bbs_bits(&b, 32);
 
   if (q != r) {