How to find integer point of a ec curve in a given range? - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2022-01-20T21:08:29Z https://crypto.stackexchange.com/feeds/question/95059 https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/95059 1 How to find integer point of a ec curve in a given range? Match Man https://crypto.stackexchange.com/users/95843 2021-09-14T14:39:12Z 2021-09-16T21:24:36Z <p>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 <code>p</code> like 17 in a discrete domain to show the points.</p> <p>I am really curious that if I can find a point with a really big <code>p</code> in practice. For example, secp256k1 is using a really big <code>p</code>=2^256−2^32−977 in domain (p,a,b,G,n,h).</p> <p>Below is the python code I use to deduct possible integer of y from solving equation with range of integer <code>x</code>. To my surprise that there is no finding even in 1 million range!</p> <p>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> <p>P.S. I am wondering how generator point <code>G</code> is selected, too. But that might need deeper understanding to the topic.</p> <pre><code>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)) &lt; 0.0001 or \ (1 - abs(math.modf(y_float)) &lt; 0.0001): # print(y_float) # bug: y_int = int(math.modf(y_float)) 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) </code></pre> <h2>Update 1</h2> <p>The previous code is wrong, since floating point sqrt() will cause unacceptable error when converting it back to integer.</p> <p>But, after replacing <code>math.sqrt()</code> to <code>math.isqrt()</code>, it still doesn't make things reasonable.</p> <h2>Update 2</h2> <p>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.</p> <p>The point is, besides using <code>%</code> for all multiplication and additions, I <strong>should</strong> also use modular square root to find the solution, <strong>instead of</strong> integer square root along with <code>%</code>. That is totally a misuse of <code>%</code> for sure.</p> <p>The modified code pass the test with some test vectors.</p> <pre><code>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 </code></pre> https://crypto.stackexchange.com/questions/95059/-/95060#95060 3 Answer by Daniel S for How to find integer point of a ec curve in a given range? Daniel S https://crypto.stackexchange.com/users/87477 2021-09-14T16:09:47Z 2021-09-14T16:09:47Z <p>I'm not quite sure what you mean by <span class="math-container">$p$</span> and I'm not sure what you meant for your code to print out.</p> <p>However, it looks like you are trying to find integer valued points on the elliptic curve <span class="math-container">$y^2=x^3+7$</span> by exhausting over <span class="math-container">$x$</span> 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 <a href="https://www.lmfdb.org/EllipticCurve/Q/21168/ce/2" rel="nofollow noreferrer">curve that you have picked</a> there are no integer points whatsoever.</p> <p>You might be trying to find integers <span class="math-container">$x$</span> and <span class="math-container">$y$</span> so that <span class="math-container">$y^2\equiv x^3+7\pmod p$</span> for some large prime <span class="math-container">$p$</span>. In this case you should take square roots mod <span class="math-container">$p$</span> rather than over the real numbers. This uses <a href="https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus" rel="nofollow noreferrer">a different computation</a>. Choosing a large prime <span class="math-container">$p$</span> and then taking any <span class="math-container">$x$</span> value has an approximately 50% chance of finding a suitable <span class="math-container">$y$</span> by taking a modular square root of <span class="math-container">$x^3+17$</span>.</p>