Quote from: Jesse James on February 04, 2015, 09:45:31 PM

Here's my attempt to restate the original problem in a way that is less ambiguous and hopefully reveal more clearly the OP's intent.

Challenge: Optimize the 'find' function in the code below so that on average it can be computed for less than 1M USD in EC2 compute cost.

Code: (python)

# http://en.wikipedia.org/wiki/Curve25519 parameters
P = 2 ** 255 - 19
A = 486662
N = 7237005577332262213973186563042994240857116359379907606001950938285454250989

def expmod(b, e, m):
   if e == 0: return 1
   t = expmod(b, e / 2, m) ** 2 % m
   if e & 1: t = (t * b) % m
   return t

def inv(x):
   return expmod(x, P - 2, P)

# doubles a point on a montgomery curve (x-coordinate only representation)
# https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#doubling-dbl-1987-m-3
def double(x1):
   xx1 = x1 * x1 % P
   x3 = (xx1 - 1) * (xx1 - 1) % P
   z3 = 4 * x1 * (xx1 * A * x1 + 1) % P
   return x3 * inv(z3) % P

def find(target, initial_point=9):
   assert 0 < target < P
   assert 0 < initial_point < P
   x = initial_point
   i = 0
   while i < N:
   if x == target:
   return i
   x = double(x)
   i += 1

Dang! I don't know Python or any programming language. Sad

But I think I can get a better idea of the question. Thanks for posting this.