Quote from: christianlundkvist on July 01, 2014, 08:51:13 PM

Quote from: dalydir on June 24, 2014, 05:32:01 AM

If anyone can make sense of:

def inverse(x, p):
"""
Calculate the modular inverse of x ( mod p )
the modular inverse is a number such that:
(inverse(x, p) * x) % p == 1
you could think of this as: 1/x
"""
inv1 = 1
inv2 = 0
while p != 1 and p!=0:
inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p

return inv2

Which is in Python, it would solve my dilemma. The commas don't make sense to me (IE: "How can a comma work with the equal sign"). That seems to be the part of my program which doesn't function correctly. Yes, my code has that as well; that's the only part of my code I don't understand piece for piece (as I had to copy and paste that part). All I'm really trying to do is to get this code to work. This code should just spit out the public key for addresses represented by the number 4 through the number 10.

The algorithm above for the modular inverse is the Extended Euclidean Algorithm, basically the algorithm will spit out an integer a with the property that a*x + b*p = 1 for some number b.

As for the commas in python, in general a,b = c,d means that a=c and b=d, and you can also do things like swapping the values of a and b by using a,b = b,a.

In our case

Code:

inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p

can be written more explicitly as

Code:

temp = inv2
inv2 = inv1 - inv2 * (x / p)
inv1 = temp

temp = p
p = x % p
x = temp

When you test the code, you can check if the value a returned by your function satisfies (a*x) % p == 1.

Just realized, the problem isn't that I'm getting a solution to the problem, its getting the wrong solution....I think. The whole result keeps giving me negative y coordinates for the public key, which, mathematically, may make sense, but its not a valid public key in it of itself. When I add "p", or the mod number to it to provide me with a positive number, it gives me a valid y coordinate, but the wrong y coordinate for the given private key.