vxgmichel · October 15, 2022 14:55 · Mar 15, 2022 · Jan 17, 2020 · Jan 17, 2020
diff --git a/timecapsule.py b/timecapsule.py
@@ -87,6 +87,6 @@ def main(t, n, gmp):
     args = parser.parse_args()
     if args.gmp and gmpy2 is None:
         parser.error(
-            "gmpy2 is not installed. Intall it using: `pip install gmpy2`"
+            "gmpy2 is not installed. Install it using: `pip install gmpy2`"
         )
     main(args.t, args.n, args.gmp)
diff --git a/timecapsule.py b/timecapsule.py
@@ -15,9 +15,9 @@
 
     % time ./timecapsule.py -t 100000 -g
     230195281883451811244330425685617[...]214563011854122010792677489171995
-    A single step takes about 4.3 nanoseconds
-    It would take 10 years and 158 days to complete
-    ./timecapsule.py -t 100000 -g  0,44s user 0,00s system 99% cpu 0,446 total
+    A single step takes about 1.2 nanoseconds
+    It would take 2 years and 323 days to complete
+    ./timecapsule.py -t 100000 -g  0,14s user 0,01s system 99% cpu 0,145 total
 
 """
 
@@ -51,14 +51,17 @@
 )
 
 
-def solve(x=2, t=T, n=N, gmp=False):
-    powmod = pow
+def solve(x=2, t=T, n=N, chunk=2**10, gmp=False):
+    e = 2 ** chunk
     if gmp:
+        x = gmpy2.mpz(x)
+        e = gmpy2.mpz(e)
         n = gmpy2.mpz(n)
-        powmod = gmpy2.powmod
-    for _ in range(t):
-        x = powmod(x, 2, n)
-    return x
+
+    q, r = divmod(t, chunk)
+    for _ in range(q):
+        x = pow(x, e, n)
+    return pow(x, 2**r, n)
 
 
 def main(t, n, gmp):

diff --git a/timecapsule.py b/timecapsule.py
@@ -0,0 +1,89 @@
+#!/usr/bin/env python3
+
+"""
+Theoretical solver of the LCS35 Time Capsule Crypto-Puzzle
+
+See: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
+
+Example usage:
+
+    % time ./timecapsule.py -t 100000
+    230195281883451811244330425685617[...]214563011854122010792677489171995
+    A single step takes about 10.3 nanoseconds
+    It would take 24 years and 261 days to complete
+    ./timecapsule.py -t 100000  1,00s user 0,00s system 99% cpu 1,009 total
+
+    % time ./timecapsule.py -t 100000 -g
+    230195281883451811244330425685617[...]214563011854122010792677489171995
+    A single step takes about 4.3 nanoseconds
+    It would take 10 years and 158 days to complete
+    ./timecapsule.py -t 100000 -g  0,44s user 0,00s system 99% cpu 0,446 total
+
+"""
+
+import sys
+import time
+import argparse
+
+try:
+    import gmpy2
+except ImportError:
+    gmpy2 = None
+
+
+T = 79_685_186_856_218
+N = int(
+    "".join(
+        """
+    631446608307288889379935712613129233236329881833084137558899
+    077270195712892488554730844605575320651361834662884894808866
+    350036848039658817136198766052189726781016228055747539383830
+    826175971321892666861177695452639157012069093997368008972127
+    446466642331918780683055206795125307008202024124623398241073
+    775370512734449416950118097524189066796385875485631980550727
+    370990439711973361466670154390536015254337398252457931357531
+    765364633198906465140213398526580034199190398219284471021246
+    488745938885358207031808428902320971090703239693491996277899
+    532332018406452247646396635593736700936921275809208629319872
+    7008292431243681
+    """.split()
+    )
+)
+
+
+def solve(x=2, t=T, n=N, gmp=False):
+    powmod = pow
+    if gmp:
+        n = gmpy2.mpz(n)
+        powmod = gmpy2.powmod
+    for _ in range(t):
+        x = powmod(x, 2, n)
+    return x
+
+
+def main(t, n, gmp):
+    start = time.time()
+    print(solve(t=t, n=n, gmp=gmp))
+    delta = time.time() - start
+    step = delta / t
+    step_ns = step * 1024 * 1024
+    days = int(step * T / 3600 / 24)
+    years, days = divmod(days, 365)
+    print(
+        f"A single step takes about {step_ns:.1f} nanoseconds\n"
+        f"It would take {years} years and {days} days to complete",
+        file=sys.stderr,
+    )
+
+
+if __name__ == "__main__":
+    parser = argparse.ArgumentParser()
+    parser.add_argument("-n", type=int, default=N)
+    parser.add_argument("-t", type=int, default=T)
+    parser.add_argument("-g", "--gmp", action="store_true")
+    args = parser.parse_args()
+    if args.gmp and gmpy2 is None:
+        parser.error(
+            "gmpy2 is not installed. Intall it using: `pip install gmpy2`"
+        )
+    main(args.t, args.n, args.gmp)
No results found