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.
# 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