* More cleanup (got rid of .wide. and .narrow.)

* Working microcode for non-CRT exponentiation (i.e. when only d is known)

1 files changed, 169 insertions, 85 deletions

diff --git a/modexpng_fpga_model.py b/modexpng_fpga_model.py
index 71a4b91..325f544 100644
--- a/modexpng_fpga_model.py
+++ b/modexpng_fpga_model.py
@@ -1085,7 +1085,7 @@ class ModExpNG_Core():
     # copy from CRT_(X|Y).LADDER_X.NARROW to OUTPUT
     #
     def set_output_from_narrow(self, sel_output, bank_crt, sel_narrow):
-        self.out._set_value(sel_output, bank_crt.ladder_x.narrow._get_value(sel_narrow))
+        self.out._set_value(sel_output, bank_crt.ladder_x._get_narrow(sel_narrow))
 
     #
     # copy from INPUT to CRT_(X|Y).LADDER_{X,Y}.NARROW
@@ -1102,7 +1102,7 @@ class ModExpNG_Core():
         bank_crt.ladder_y._set_wide(sel_wide, self.inp._get_value(sel_input))
 
     #
-    # copy from CRT_Y.LADDER_{X,Y).{WIDE,NARROW} to CRT_X.LADDER_{X,Y}.{WIDE,NARROW}
+    # copy from CRT_Y.LADDER_{X,Y}.{WIDE,NARROW} to CRT_X.LADDER_{X,Y}.{WIDE,NARROW}
     #
     def copy_crt_y2x(self, sel_wide, sel_narrow):
 
@@ -1124,6 +1124,17 @@ class ModExpNG_Core():
         self.bnk.crt_y.ladder_y._set_narrow(sel_narrow_out, self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in))
 
     #
+    # copy from CRT_{X,Y}.LADDER_Y.{WIDE,NARROW} to CRT_{X,Y}.LADDER_X.{WIDE,NARROW}
+    #
+    def copy_ladders_y2x(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out):
+
+        self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, self.bnk.crt_x.ladder_y._get_wide(sel_wide_in))
+        self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, self.bnk.crt_y.ladder_y._get_wide(sel_wide_in))
+
+        self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, self.bnk.crt_x.ladder_y._get_narrow(sel_narrow_in))
+        self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in))
+
+    #
     # copy from CRT_{X,Y}.LADDER_X.{WIDE,NARROW} to CRT_{Y,X}.LADDER_Y.{WIDE,NARROW}
     #
     def cross_ladders_x2y(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out):
@@ -1143,23 +1154,23 @@ class ModExpNG_Core():
     #
     def modular_multiply(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out, num_words, mode=(True, True), d=False):
 
-        xn       = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
-        yn       = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
+        xn       = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
+        yn       = self.bnk.crt_y.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
 
-        xn_coeff = self.bnk.crt_x.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
-        yn_coeff = self.bnk.crt_y.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
+        xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
+        yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
 
-        xxa       = self.bnk.crt_x.ladder_x.wide._get_value(sel_wide_in)
-        xya       = self.bnk.crt_x.ladder_y.wide._get_value(sel_wide_in)
+        xxa       = self.bnk.crt_x.ladder_x._get_wide(sel_wide_in)
+        xya       = self.bnk.crt_x.ladder_y._get_wide(sel_wide_in)
 
-        yxa       = self.bnk.crt_y.ladder_x.wide._get_value(sel_wide_in)
-        yya       = self.bnk.crt_y.ladder_y.wide._get_value(sel_wide_in)
+        yxa       = self.bnk.crt_y.ladder_x._get_wide(sel_wide_in)
+        yya       = self.bnk.crt_y.ladder_y._get_wide(sel_wide_in)
 
-        xxb       = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in)
-        xyb       = self.bnk.crt_x.ladder_y.narrow._get_value(sel_narrow_in)
+        xxb       = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in)
+        xyb       = self.bnk.crt_x.ladder_y._get_narrow(sel_narrow_in)
 
-        yxb       = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in)
-        yyb       = self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow_in)
+        yxb       = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in)
+        yyb       = self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in)
 
         if not mode[0]: xb = xxb
         else:           xb = xyb
@@ -1189,22 +1200,22 @@ class ModExpNG_Core():
     #
     def modular_subtract(self, sel_narrow_in, sel_narrow_out, sel_wide_out, num_words):
 
-        xa = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in)
-        xb = self.bnk.crt_x.ladder_y.narrow._get_value(sel_narrow_in)
-        xn = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
+        xa = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in)
+        xb = self.bnk.crt_x.ladder_y._get_narrow(sel_narrow_in)
+        xn = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
 
-        ya = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in)
-        yb = self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow_in)
-        yn = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
+        ya = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in)
+        yb = self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in)
+        yn = self.bnk.crt_y.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
 
         xd = self.wrk.serial_subtract_modular(xa, xb, xn, num_words)
         yd = self.wrk.serial_subtract_modular(ya, yb, yn, num_words)
 
-        self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow_out, xd)
-        self.bnk.crt_y.ladder_x.narrow._set_value(sel_narrow_out, yd)
+        self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, xd)
+        self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, yd)
 
-        self.bnk.crt_x.ladder_x.wide._set_value(sel_wide_out, xd)
-        self.bnk.crt_y.ladder_x.wide._set_value(sel_wide_out, yd)
+        self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, xd)
+        self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, yd)
     
     #
     # modular reduce sel_narrow_in
@@ -1212,27 +1223,27 @@ class ModExpNG_Core():
     #
     def modular_reduce(self, sel_narrow_in, sel_wide_out, sel_narrow_out, num_words):
 
-        xn       = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
-        yn       = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
+        xn       = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
+        yn       = self.bnk.crt_y.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
 
-        xn_coeff = self.bnk.crt_x.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
-        yn_coeff = self.bnk.crt_y.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
+        xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
+        yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
 
-        xb       = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in)
-        yb       = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in)
+        xb       = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in)
+        yb       = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in)
 
         xp = self.wrk.multipurpose_multiply(None, xb, xn, xn_coeff, num_words, reduce_only=True)
         yp = self.wrk.multipurpose_multiply(None, yb, yn, yn_coeff, num_words, reduce_only=True)
 
-        self.bnk.crt_x.ladder_x.wide._set_value(sel_wide_out, xp)
-        self.bnk.crt_x.ladder_y.wide._set_value(sel_wide_out, xp)
-        self.bnk.crt_y.ladder_x.wide._set_value(sel_wide_out, yp)
-        self.bnk.crt_y.ladder_y.wide._set_value(sel_wide_out, yp)
+        self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, xp)
+        self.bnk.crt_x.ladder_y._set_wide(sel_wide_out, xp)
+        self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, yp)
+        self.bnk.crt_y.ladder_y._set_wide(sel_wide_out, yp)
 
-        self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow_out, xp)
-        self.bnk.crt_x.ladder_y.narrow._set_value(sel_narrow_out, xp)
-        self.bnk.crt_y.ladder_x.narrow._set_value(sel_narrow_out, yp)
-        self.bnk.crt_y.ladder_y.narrow._set_value(sel_narrow_out, yp)
+        self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, xp)
+        self.bnk.crt_x.ladder_y._set_narrow(sel_narrow_out, xp)
+        self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, yp)
+        self.bnk.crt_y.ladder_y._set_narrow(sel_narrow_out, yp)
 
     #
     # propagate carries (convert to non-redundant representation) content in sel_narrow
@@ -1274,20 +1285,20 @@ class ModExpNG_Core():
     #
     def regular_multiply(self, sel_wide_in, sel_narrow_in, num_words):
 
-        xn       = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
-        yn       = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N)
+        xn       = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
+        yn       = self.bnk.crt_y.ladder_x._get_wide(ModExpNG_WideBankEnum.N)
 
-        xn_coeff = self.bnk.crt_x.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
-        yn_coeff = self.bnk.crt_y.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF)
+        xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
+        yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF)
 
-        xxa       = self.bnk.crt_x.ladder_x.wide._get_value(sel_wide_in)
-        xya       = self.bnk.crt_x.ladder_y.wide._get_value(sel_wide_in)
+        xxa       = self.bnk.crt_x.ladder_x._get_wide(sel_wide_in)
+        xya       = self.bnk.crt_x.ladder_y._get_wide(sel_wide_in)
 
-        yxa       = self.bnk.crt_y.ladder_x.wide._get_value(sel_wide_in)
-        yya       = self.bnk.crt_y.ladder_y.wide._get_value(sel_wide_in)
+        yxa       = self.bnk.crt_y.ladder_x._get_wide(sel_wide_in)
+        yya       = self.bnk.crt_y.ladder_y._get_wide(sel_wide_in)
 
-        xb       = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in)
-        yb       = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in)
+        xb       = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in)
+        yb       = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in)
 
         xxp = self.wrk.multipurpose_multiply(xxa, xb, None, None, num_words, multiply_only=True)
         xyp = self.wrk.multipurpose_multiply(xya, xb, None, None, num_words, multiply_only=True)
@@ -1307,15 +1318,15 @@ class ModExpNG_Core():
         yyp_lsb = yyp.lower_half()
         yyp_msb = yyp.upper_half()
 
-        self.bnk.crt_x.ladder_x.wide._set_value(ModExpNG_WideBankEnum.L, xxp_lsb)
-        self.bnk.crt_x.ladder_y.wide._set_value(ModExpNG_WideBankEnum.L, xyp_lsb)
-        self.bnk.crt_y.ladder_x.wide._set_value(ModExpNG_WideBankEnum.L, yxp_lsb)
-        self.bnk.crt_y.ladder_y.wide._set_value(ModExpNG_WideBankEnum.L, yyp_lsb)
+        self.bnk.crt_x.ladder_x._set_wide(ModExpNG_WideBankEnum.L, xxp_lsb)
+        self.bnk.crt_x.ladder_y._set_wide(ModExpNG_WideBankEnum.L, xyp_lsb)
+        self.bnk.crt_y.ladder_x._set_wide(ModExpNG_WideBankEnum.L, yxp_lsb)
+        self.bnk.crt_y.ladder_y._set_wide(ModExpNG_WideBankEnum.L, yyp_lsb)
 
-        self.bnk.crt_x.ladder_x.wide._set_value(ModExpNG_WideBankEnum.H, xxp_msb)
-        self.bnk.crt_x.ladder_y.wide._set_value(ModExpNG_WideBankEnum.H, xyp_msb)
-        self.bnk.crt_y.ladder_x.wide._set_value(ModExpNG_WideBankEnum.H, yxp_msb)
-        self.bnk.crt_y.ladder_y.wide._set_value(ModExpNG_WideBankEnum.H, yyp_msb)
+        self.bnk.crt_x.ladder_x._set_wide(ModExpNG_WideBankEnum.H, xxp_msb)
+        self.bnk.crt_x.ladder_y._set_wide(ModExpNG_WideBankEnum.H, xyp_msb)
+        self.bnk.crt_y.ladder_x._set_wide(ModExpNG_WideBankEnum.H, yxp_msb)
+        self.bnk.crt_y.ladder_y._set_wide(ModExpNG_WideBankEnum.H, yyp_msb)
 
     #
     # adds sel_narrow_a_in to sel_narrow_b_in
@@ -1345,7 +1356,7 @@ class ModExpNG_Core():
     #
     # dump working variables before ladder step
     #
-    def dump_before_step_crt(self, pq, m):
+    def dump_before_step_using_crt(self, pq, m):
         print("num_words = %d" % pq)
         print("\rladder_mode_x = %d" % m[0])
         print("\rladder_mode_y = %d" % m[1])
@@ -1361,7 +1372,7 @@ class ModExpNG_Core():
     #
     # dump working variables after ladder step
     #
-    def dump_after_step_crt(self):
+    def dump_after_step_using_crt(self):
         self.bnk.crt_x.ladder_x._get_narrow(N.C).format_verilog_concat("X_X")
         self.bnk.crt_x.ladder_y._get_narrow(N.C).format_verilog_concat("X_Y")
         self.bnk.crt_y.ladder_x._get_narrow(N.C).format_verilog_concat("Y_X")
@@ -1430,6 +1441,17 @@ def get_ladder_mode_using_crt(v, bit):
     return (bit_value_p, bit_value_q)
 
 #
+# get current ladder mode based on private exponent's bit
+#
+def get_ladder_mode_without_crt(v, bit):
+
+    bit_value_d = (v.d.number() & (1 << bit)) >> bit
+
+    bit_value_d = bit_value_d > 0
+
+    return (not bit_value_d, bit_value_d)
+
+#
 # print current exponentiation progress
 #
 def print_ladder_progress(current, total):
@@ -1487,7 +1509,7 @@ def sign_using_crt():
     c.set_output_from_narrow(O.XM, c.bnk.crt_x, N.D)               # | [XY] / N_FACTOR        | [XY]F | [XY]YM           | [XY]M   | M         |
     c.set_output_from_narrow(O.YM, c.bnk.crt_y, N.D)               # | [XY] / N_FACTOR        | [XY]F | [XY]YM           | [XY]M   | M         |
                                                                    # +------------------------+-------+------------------+---------+-----------+
-    c.modular_multiply(W.E, N.B, W.C, N.C, n)                      # | [XY] / N_FACTOR        | [XY]F | [XY]MB           | [XY]M   | M         | [XY]MB = M*[XY]F
+    c.modular_multiply(W.E, N.B, W.C, N.C, n)                      # | [XY] / N_FACTOR        | [XY]F | [XY]MB           | [XY]M   | M         | [XY]MB = M * [XY]F
                                                                    # +------------------------+-------+------------------+---------+-----------+
     c.propagate_carries(N.C, n_num_words)                          # | [XY] / N_FACTOR        | [XY]F | [XY]MB           | [XY]M   | M         |
                                                                    # +------------------------+-------+------------------+---------+-----------+
@@ -1508,7 +1530,6 @@ def sign_using_crt():
     c.set_narrow_from_input(c.bnk.crt_x, N.E,       I.QINV)        # | [PQ]_FACTOR            | [XY]F |  YMB             | [XY]M   | QINV      |
                                                                    # +------------------------+-------+------------------+---------+-----------+
     c.modular_reduce(N.C, W.D, N.D, pq)                            # | [PQ]_FACTOR            | [XY]F |  YMB             | [PQ]MBZ | QINV      | [PQ]MBZ = YMB mod [PQ]
-                                                                   # +------------------------+-------+------------------+---------+-----------+
     c.modular_multiply(W.D, N.A, W.C, N.C, pq)                     # | [PQ]_FACTOR            | [XY]F | [PQ]MB           | [PQ]MBZ | QINV      | [PQ]MB = [PQ]MBZ * [PQ]_FACTOR
     c.modular_multiply(W.C, N.A, W.D, N.D, pq)                     # | [PQ]_FACTOR            | [XY]F | [PQ]MB           | [PQ]MBF | QINV      | [PQ]MBF = [PQ]MB * [PQ]_FACTOR
     c.modular_multiply(W.A, N.I, W.C, N.C, pq)                     # | [PQ]_FACTOR            | [XY]F | [PQ]IF           | [PQ]MBF | QINV      | [PQ]IF = 1 * [PQ]_FACTOR
@@ -1526,11 +1547,11 @@ def sign_using_crt():
                                                                    # |                        |       |                  |         |           |
         if dbg:                                                    # |                        |       |                  |         |           |
             if FORCE_OVERFLOW: c._force_overflow(c.bnk.crt_x, N.C) # |                        |       |                  |         |           |
-            if DUMP_VECTORS: c.dump_before_step_crt(pq, m)         # |                        |       |                  |         |           |
+            if DUMP_VECTORS: c.dump_before_step_using_crt(pq, m)   # |                        |       |                  |         |           |
                                                                    # +------------------------+-------+------------------+---------+-----------+
         c.modular_multiply(W.C, N.C, W.C, N.C, pq, mode=m, d=dbg)  # | [PQ]_FACTOR            | [XY]F | [PQ]SBF          | [PQ]MBF | QINV      | <LADDER>
                                                                    # +------------------------+-------+------------------+---------+-----------+
-        if dbg and DUMP_VECTORS: c.dump_after_step_crt()           # |                        |       |                  |         |           |
+        if dbg and DUMP_VECTORS: c.dump_after_step_using_crt()     # |                        |       |                  |         |           |
         print_ladder_progress(bit, pq)                             # |                        |       |                  |         |           |
                                                                    # |                        |       |                  |         |           |
     #########################                                      # |                        |       |                  |         |           |
@@ -1576,6 +1597,87 @@ def sign_using_crt():
                                                                    # +------------------------+-------+------------------+---------+-----------+
     c.set_output_from_narrow(O.S, c.bnk.crt_x, N.A)                # |  S                     |       |                  |         |           |
                                                                    # +------------------------+-------+------------------+---------+-----------+
+
+#
+# try to exponentiate using only half of the quad-multiplier (one dual-ladder core)
+#
+def sign_without_crt():
+
+    c  = core
+    v  = vector
+    n  = n_num_words
+
+    ff = (False, False)
+
+    c.set_wide_from_input   (c.bnk.crt_x, W.N,       I.N)
+    c.set_wide_from_input   (c.bnk.crt_y, W.N,       I.N)
+    c.set_wide_from_input   (c.bnk.crt_x, W.A,       I.X)
+    c.set_wide_from_input   (c.bnk.crt_y, W.A,       I.Y)
+    c.set_wide_from_input   (c.bnk.crt_x, W.E,       I.M)
+    c.set_wide_from_input   (c.bnk.crt_y, W.E,       I.M)
+
+    c.set_narrow_from_input (c.bnk.crt_x, N.N_COEFF, I.N_COEFF)
+    c.set_narrow_from_input (c.bnk.crt_y, N.N_COEFF, I.N_COEFF)
+    c.set_narrow_from_input (c.bnk.crt_x, N.A,       I.N_FACTOR)
+    c.set_narrow_from_input (c.bnk.crt_y, N.A,       I.N_FACTOR)
+    c.set_narrow_from_input (c.bnk.crt_x, N.E,       I.M)
+    c.set_narrow_from_input (c.bnk.crt_y, N.E,       I.M)
+
+    c.modular_multiply(W.A, N.A, W.B, N.B, n)           # [XY]F = [XY] * N_FACTOR
+    c.modular_multiply(W.B, N.B, W.C, N.C, n, mode=ff)  # [XY]MF = [XY]F * [XY]F
+    c.modular_multiply(W.C, N.I, W.D, N.D, n)           # [XY]M = [XY]MF * 1
+
+    c.propagate_carries(N.D, n)
+
+    c.set_output_from_narrow(O.XM, c.bnk.crt_x, N.D)
+    c.set_output_from_narrow(O.YM, c.bnk.crt_y, N.D)
+
+    c.modular_multiply(W.E, N.B, W.C, N.C, n)   # [XY]MB = M * [XY]F
+
+    XF = c.bnk.crt_x.ladder_x._get_narrow(N.B)
+
+    c.set_wide_from_input(c.bnk.crt_x, W.A, I.N_FACTOR)
+    c.set_wide_from_input(c.bnk.crt_y, W.A, I.N_FACTOR)
+
+    c.modular_multiply(W.C, N.A, W.D, N.D, n)   # MBF = MB * N_FACTOR
+    c.modular_multiply(W.A, N.I, W.C, N.C, n)   # IF = 1 * N_FACTOR    
+    
+    c.copy_ladders_x2y(W.D, N.D, W.C, N.C)
+
+    ###########################
+    # Begin Montgomery Ladder #
+    ###########################
+
+    for bit in range(_WORD_WIDTH * n - 1, -1, -1):
+
+        m  = get_ladder_mode_without_crt(v, bit)
+        dbg = bit == DUMP_LADDER_INDEX
+
+        if dbg:
+            if FORCE_OVERFLOW: c._force_overflow(c.bnk.crt_x, N.C)
+            if DUMP_VECTORS: c.dump_before_step_without_crt(n, m)
+
+        c.modular_multiply(W.C, N.C, W.C, N.C, n, mode=m, d=dbg)
+
+        if dbg and DUMP_VECTORS: c.dump_after_step_without_crt()
+        print_ladder_progress(bit, n)
+            
+    #########################
+    # End Montgomery Ladder #
+    #########################
+
+    c.cross_ladders_x2y(W.B, N.B, W.B, N.B)
+
+    c.modular_multiply(W.C, N.I, W.D, N.D, n)           # SB = SBF * 1    
+    c.modular_multiply(W.B, N.D, W.A, N.A, n, mode=ff)  # S = XF * SB
+
+    c.copy_ladders_y2x(W.A, N.A, W.B, N.B)
+    
+    c.propagate_carries(N.B, n)
+    
+    c.set_output_from_narrow(O.S, c.bnk.crt_y, N.B)
+
+
 #
 # main()
 #
@@ -1627,35 +1729,17 @@ if __name__ == "__main__":
     xm_known = pow(vector.x.number(), 2, vector.n.number())
     ym_known = pow(vector.y.number(), 2, vector.n.number())
 
-    # sign using CRT
+    # sign using CRT and check
     print("Signing using CRT...")
     sign_using_crt()
     compare_signature()
 
-    # sign without CRT
-    # ...
+    # sign without CRT and check
+    print("Signing without CRT...")
+    sign_without_crt()
+    compare_signature()
 
 
 #
 # End-of-File
 #
-
-
-
-    # bring one into Montgomery domain (glue 2**r to one)
-    # bring blinding coefficients into Montgomery domain (glue 2**(2*r) to x and y)
-    # blind message
-    # convert message to non-redundant representation
-    # first reduce message, this glues 2**-r to the message as a side effect
-    # unglue 2**-r from message by gluing 2**r to it to compensate
-    # bring message into Montgomery domain (glue 2**r to message)
-    # do "easier" exponentiations
-    # return "easier" parts from Montgomery domain (unglue 2**r from result)
-    # do the "Garner's formula" part
-    #  r = sp - sq mod p
-    #  sr_qinv = sr * qinv mod p
-    #  q_sr_qinv = q * sr_qinv
-    #  s_crt = sq + q_sr_qinv
-    # unblind s
-    # mutate blinding factors
-