Add cyclic group abstraction, with test code. Separate off exponentation

[u/mdw/catacomb] / pcheck.pl

diff --git a/pcheck.pl b/pcheck.pl
new file mode 100644 (file)
index 0000000..354b0f6
--- /dev/null
+++ b/pcheck.pl
@@ -0,0 +1,43 @@
+#! /usr/bin/perl
+
+# Reads ptab.in or similarly-formatted file; writes a calc script to check
+# it.
+
+while (<>) {
+  next if /^\s*(\#[^!]|$)/;
+  @F = split;
+  if ($F[0] eq "group") {
+    $group = $F[1];
+    $_ = <>; @F = split; $F[0] eq "p" or die $F[0]; $p = $F[1];
+    $_ = <>; @F = split; $F[0] eq "q" or die $F[0]; $q = $F[1];
+    $_ = <>; @F = split; $F[0] eq "g" or die $F[0]; $g = $F[1];
+    print <<EOF;
+      print "testing $group...";
+      p = $p;
+      q = $q;
+      g = $g;
+      if (!ptest(p)) print "  p not prime";
+      if (!ptest(q)) print "  q not prime";
+      if ((p - 1)%q) print "  q doesn't divide p - 1";
+      h = (p - 1)/q;
+      if (pmod(g, q, p) != 1) print "  g doesn't have order q";
+      if (pmod(g, h, p) == 1) print "  g generates overly large group";
+      ff = 2;
+EOF
+    $ll = 0;
+    for (;;) {
+      $_ = <>; @F = split; $F[0] eq "#:factor" or last; $f = $F[1];
+      print <<EOF;
+        f = $f;
+        if (!ptest(f)) print "  factor not prime", f;
+        ff *= f;
+EOF
+      $ll = 1;
+    }
+    if ($ll) {
+      print <<EOF;
+        if (ff != p - 1) print "  missing factors";
+EOF
+    }
+  }
+}