New program gen-jacobitab.

1 files changed, 117 insertions, 0 deletions

diff --git a/gen-jacobitab.c b/gen-jacobitab.c
new file mode 100644
index 000000000..261e5c074
--- /dev/null
+++ b/gen-jacobitab.c
@@ -0,0 +1,117 @@
+/* gen-jacobi.c
+
+   Contributed to the GNU project by Niels Möller.
+
+Copyright 2010 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library 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 Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library.	If not, see http://www.gnu.org/licenses/.  */
+
+/* Generate the lookup table needed for fast left-to-right computation
+   of the Jacobi symbol. */
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+static const struct
+{
+  unsigned char a;
+  unsigned char b;
+} decode_table[13] = {
+  /*  0 */ { 0, 1 },
+  /*  1 */ { 0, 3 },
+  /*  2 */ { 1, 1 },
+  /*  3 */ { 1, 3 },
+  /*  4 */ { 2, 1 },
+  /*  5 */ { 2, 3 },
+  /*  6 */ { 3, 1 },
+  /*  7 */ { 3, 3 }, /* d = 1 */
+  /*  8 */ { 1, 0 },
+  /*  9 */ { 1, 2 },
+  /* 10 */ { 3, 0 },
+  /* 11 */ { 3, 2 },
+  /* 12 */ { 3, 3 }, /* d = 0 */
+  
+};
+#define JACOBI_A(bits) (decode_table[(bits)>>1].a)
+#define JACOBI_B(bits) (decode_table[(bits)>>1].b)
+
+#define JACOBI_E(bits) ((bits) & 1)
+#define JACOBI_D(bits) (((bits)>>1) == 7) /* Gives 0 for don't care states. */
+
+static unsigned
+encode (unsigned a, unsigned b, unsigned d)
+{
+  unsigned i;
+  
+  assert (d < 2);
+  assert (a < 4);
+  assert (b < 4);
+  assert ( (a | b ) & 1);
+
+  if (a == 3 && b == 3)
+    return d ? 7 : 12;
+
+  for (i = 0; i < 12; i++)
+    if (decode_table[i].a == a
+	&& decode_table[i].b == b)
+      return i;
+
+  abort ();
+}
+
+int
+main (int argc, char **argv)
+{
+  unsigned bits;
+
+  for (bits = 0; bits < 208; bits++)
+    {
+      unsigned e, a, b, d_old, d, q;
+
+      if (bits && !(bits & 0xf))
+	printf("\n");
+
+      q = bits & 3;
+      d = (bits >> 2) & 1;
+      
+      e = JACOBI_E (bits >> 3);
+      a = JACOBI_A (bits >> 3);
+      b = JACOBI_B (bits >> 3);
+      d_old = JACOBI_D (bits >> 3);
+
+      if (d != d_old && a == 3 && b == 3)
+	e ^= 1;
+
+      if (d == 1)
+	{
+	  if (b == 2)
+	    e ^= (q & (a >> 1)) ^ (q >> 1);
+	  a = (a - q * b) & 3;
+	}
+      else
+	{
+	  if (a == 2)
+	    e ^= (q & (b >> 1)) ^ (q >> 1);
+	  b = (b - q * a) & 3;
+	}
+      
+      printf("%2d,", (encode (a, b, d) << 1) | e);
+    }
+  printf("\n");
+  
+  return 0;
+}