math/f25519.c: Implementation for arithmetic in GF(2^255 - 19).

[catacomb] / utils / curve25519.sage

diff --git a/utils/curve25519.sage b/utils/curve25519.sage
new file mode 100644 (file)
index 0000000..32ddb17
--- /dev/null
+++ b/utils/curve25519.sage
@@ -0,0 +1,43 @@
+#! /usr/local/bin/sage
+### -*- mode: python; coding: utf-8 -*-
+
+###--------------------------------------------------------------------------
+### Define the field.
+
+p = 2^255 - 19; k = GF(p)
+
+###--------------------------------------------------------------------------
+### Arithmetic implementation.
+
+def sqrn(x, n):
+  for i in xrange(n): x = x*x
+  return x
+
+def inv(x):
+  t2 = sqrn(x, 1)        #   1 | 2
+  u = sqrn(t2, 2)        #   3 | 8
+  t = u*x                #   4 | 9
+  t11 = t*t2             #   5 | 11
+  u = sqrn(t11, 1)       #   6 | 22
+  t = u*t                #   7 | 2^5 - 1 = 31
+  u = sqrn(t, 5)         #  12 | 2^10 - 2^5
+  t2p10m1 = u*t          #  13 | 2^10 - 1
+  u = sqrn(t2p10m1, 10)  #  23 | 2^20 - 2^10
+  t = u*t2p10m1          #  24 | 2^20 - 1
+  u = sqrn(t, 20)        #  44 | 2^40 - 2^20
+  t = u*t                #  45 | 2^40 - 1
+  u = sqrn(t, 10)        #  55 | 2^50 - 2^10
+  t2p50m1 = u*t2p10m1    #  56 | 2^50 - 1
+  u = sqrn(t2p50m1, 50)  # 106 | 2^100 - 2^50
+  t = u*t2p50m1          # 107 | 2^100 - 1
+  u = sqrn(t, 100)       # 207 | 2^200 - 2^100
+  t = u*t                # 208 | 2^200 - 1
+  u = sqrn(t, 50)        # 258 | 2^250 - 2^50
+  t = u*t2p50m1          # 259 | 2^250 - 1
+  u = sqrn(t, 5)         # 264 | 2^255 - 2^5
+  t = u*t11              # 265 | 2^255 - 21
+  return t
+
+assert inv(k(9))*9 == 1
+
+###----- That's all, folks --------------------------------------------------