NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Table of Square Roots.

Rabin's cryptosystem makes use of square roots modulo n = p*q, where p and q are primes both equal to 3 modulo 4. The program below, however, works with any two primes and produces a table of all square roots. Those square roots with a factor in common with either p or q are shown in the table in red italic.

---

Java code to produce the table below or any other similar table.

// SquareTable.java: create table of squares and square roots
public class SquareTable {

   // Link: to allow linked lists of square roots
   private class Link {
      int entry; // square root entry
      Link next; // next link
   }

   private Link[] table; // table entry for each possible square
   private int p, q, n; // primes and product

   // SquareTable: constructor, passes in the primes
   public SquareTable(int pIn, int qIn) {
      p = pIn; q = qIn; n = p*q;
      table = new Link[n];
   }

   // buildTable: construct the table: array of linked lists
   public void buildTable() {
      for (int i = 1; i < n; i++) {
         int iSqr = i*i % n;
         Link link = new Link();
         Link ptr;
         if (table[iSqr] == null) {
            table[iSqr] = link;
         }
         else {
            ptr = table[iSqr];
            while (ptr.next != null)
               ptr = ptr.next;
            ptr.next = link;
         }
         link.entry = i;
         link.next = null;
      }
   }

   // printTable: print the table in HTML form
   public void printTable() {
      boolean div; // for entries with either prime as divisor
      System.out.println("<table border>");
      System.out.println("<tr><th colspan=2>Numbers mod " + n +
         " = " + p + "*" + q + "</th><tr>");
      System.out.println("<tr><th>Square</th>");
      System.out.println("<th>Square Roots</th></tr>");
      System.out.println("<tr><td></td><td></td></tr>");

      for (int j = 1; j < n; j++) {
         div = false;
         if (j%p == 0 || j%q == 0) div = true;
         if (table[j] != null) {
            System.out.print("<tr><td>");
            if (div)
               System.out.print("<font color=FF0000><i>" + 
                  j + "</i></font>");
            else
               System.out.print(j);
            System.out.print("</td><td>");
            if (div)
               System.out.print("<font color=FF0000><i>");
            Link loc = table[j];
            while (loc != null) {
               System.out.print(loc.entry);
               if (loc.next != null)
                  System.out.print(", ");
               loc = loc.next;
            }
            if (div)
               System.out.print("</i></font>");
            System.out.println("</td></tr>");
         }
      }
      System.out.println("</table>");
   }

   // main: feed in primes p and q from command line
   public static void main(String[] args) {
      SquareTable squareTable = new SquareTable(
          Integer.parseInt(args[0]), Integer.parseInt(args[1]));
      squareTable.buildTable();
      squareTable.printTable();
   }
}

---

Here is a table with p = 7, q = 11, and n = p*q = 77. Notice that the red italic entries all have either 7 or 11 as a factor. Notice also the symmetry: if s is a square root, then so is n - s.

Numbers mod 77 = 7*11
Square	Square Roots
1	1, 34, 43, 76
4	2, 9, 68, 75
9	3, 25, 52, 74
11	33, 44
14	28, 49
15	13, 20, 57, 64
16	4, 18, 59, 73
22	22, 55
23	10, 32, 45, 67
25	5, 16, 61, 72
36	6, 27, 50, 71
37	24, 31, 46, 53
42	14, 63
44	11, 66
49	7, 70
53	19, 30, 47, 58
56	21, 56
58	17, 38, 39, 60
60	26, 37, 40, 51
64	8, 36, 41, 69
67	12, 23, 54, 65
70	35, 42
71	15, 29, 48, 62