Join Log in
Score:1
Match Man avatar Crypto

How to find integer point of a ec curve in a given range?

it flag
Match Man

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a discrete domain to show the points.

I am really curious that if I can find a point with a really big p in practice. For example, secp256k1 is using a really big p=2^256−2^32−977 in domain (p,a,b,G,n,h).

Below is the python code I use to deduct possible integer of y from solving equation with range of integer x. To my surprise that there is no finding even in 1 million range!

So my question is, is below code right? And secondly, if it is right or corrected by some real expert, which value range should I try?

P.S. I am wondering how generator point G is selected, too. But that might need deeper understanding to the topic.

import math

# secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
A = 0
B = 7

# nist P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291

def in_curve(x):
    curve = x**3 + A*x + B
    y_float = math.sqrt(curve)
    if abs(math.modf(y_float)[0]) < 0.0001 or \
          (1 - abs(math.modf(y_float)[0]) < 0.0001):
        # print(y_float)
        # bug: y_int = int(math.modf(y_float)[1])
        y_int = int(round(y_float))
        if y_int * y_int == (curve):
            print(y_int)
            return y_int
    return None
 
for x in range(1, 1000000):
    y = in_curve(x)
    if y is not None:
        print(x, y)

Update 1

The previous code is wrong, since floating point sqrt() will cause unacceptable error when converting it back to integer.

But, after replacing math.sqrt() to math.isqrt(), it still doesn't make things reasonable.

Update 2

Thanks to the tips from all replied in the thread. Using generator point to verify my algorithm, I now clearly know why I was failing.

The point is, besides using % for all multiplication and additions, I should also use modular square root to find the solution, instead of integer square root along with %. That is totally a misuse of % for sure.

The modified code pass the test with some test vectors.

import modular_sqrt
#  e.g. I was using code from https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# please ask permission if usage is beyond educational hobbyist area and always list the credit being a decent human ;-)

# nist P256, taken from https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109

def get_y_in_curve(x):
    y2 = x**3 + A*x + B
    y_int = modular_sqrt(y2, P)
    if y_int and ((y_int * y_int) % P) == (y2 % P):
        return y_int
    return None

assert get_y_in_curve(Gx) == Gy
159
0 + 0
fgrieu avatar
ng flag
fgrieu
The code is incorrect. Main issue is that Elliptic Curve crypto does not work with $x$ and $y$ in an infinite set. It uses a [finite field](https://en.wikipedia.org/wiki/Finite_field). secp256k1 uses the field $\mathbb F_p$, also the [ring of integers modulo](https://en.wikipedia.org/w/index.php?title=Ring_of_integers_modulo_n) $p$. Thus the code should compute it's `curve` reduced modulo `P`, and compute (when it exists) a modular square root of that; see [this](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) for one method. Please improve or close the question.
0
Reply
Match Man avatar
it flag
Match Man
@fgrieu Yes, I realized my mistake right after Daniel pointed it out. Now the question is updated with corrected algorithm. Do you want me to close the question since it *was* wrong? Or keep it as an example of how things should be done with in Finite space of ECC. Or even just how things could go wrong when hooping from infinite space "curve" to finite space? :)
0
Reply
fgrieu avatar
ng flag
fgrieu
The updated question is OK. Since the answer helped, I think the best is to accept it, and all will be fine. Note on the new code: it would be more elegant to rename `curve` to `y2` ; compute it modulo `P` earlier on (e.g. `y2 = (x**3 + A*x + B) % P` or `y2 = (pow(x, 3, P) + A*x + B) % P)` ; and to reuse it in `y_int = modular_sqrt(y2)` and `if ((y_int * y_int) % P) == y2:`. It's not immediately clear what `modular_sqrt` does when it fails. Independently, is using another person's `modular_sqrt` OK in the context? That's the involved part!
0
Reply
Match Man avatar
it flag
Match Man
The code is refactored. modular_sqrt will return 0 for failure and new code also added that check. I don't use Eli's code directly but refer his code as an example.
1
Reply
Score:3
Daniel S avatar Crypto
ru flag
Daniel S

I'm not quite sure what you mean by $p$ and I'm not sure what you meant for your code to print out.

However, it looks like you are trying to find integer valued points on the elliptic curve $y^2=x^3+7$ by exhausting over $x$ values and I can't spot a bug other than the print statement. BUT Siegel showed that in general elliptic curves over the rational numbers only have a finite number of integer valued points and we expect these to be very rare indeed. In fact for the curve that you have picked there are no integer points whatsoever.

You might be trying to find integers $x$ and $y$ so that $y^2\equiv x^3+7\pmod p$ for some large prime $p$. In this case you should take square roots mod $p$ rather than over the real numbers. This uses a different computation. Choosing a large prime $p$ and then taking any $x$ value has an approximately 50% chance of finding a suitable $y$ by taking a modular square root of $x^3+17$.

0 + 0
Match Man avatar
it flag
Match Man
I added the meaning of `p` in question. It is so big so that I don't have to do modulation with any small number like 1 billion... > In fact for the curve that you have picked there are no integer points whatsoever. < So there is some round up operation when calculating `secp256k1`? Wonder how it goes.
0
Reply
Daniel S avatar
ru flag
Daniel S
Oh I see. In that case, if you try to generate points without using any modular arithmetic, it won't work because they would then be integral points and there are none on this curve. Note that "small" numbers that are not perfect squares can still have square roots mod $p$ if one is prepared to use modular arithmetic.
1
Reply
Match Man avatar
it flag
Match Man
Do you mean that I should change if y_int * y_int == (x^3 + 7) to if y_int * y_int == (x^3 + 7) % P, where P =2^256−2^32−977? My understanding is that secp256k1 is defined over ℤp, so previous floating point calculation is just to find if y is close enough to be an integer. There are really a lot of possible candidates in 1 million but none of them is really one...
0
Reply
Daniel S avatar
ru flag
Daniel S
No. I mean that (using the fact that $p\equiv 3\pmod 4$), you should replace y_float=math.sqrt(x^3+7) with y_int=pow(x^3+7,(p+1)/4,p) and then check if y_int*y_int==(x^3+7)%p. This won't give you a small value of $y$, but there is not a solution with a small value of both $x$ and $y$. Check out the link on computing square roots mod $p$.
1
Reply
Match Man avatar
it flag
Match Man
Got it. Question is updated with correct operation now. Thanks.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.