Post
Topic
Board Development & Technical Discussion
Merits 18 from 5 users
Topic OP
Smaller elliptic curves y^2=x^3+7, based on secp256k1
by
garlonicon
on 09/07/2023, 11:20:50 UTC
⭐ Merited by Welsh (8) ,vapourminer (5) ,vjudeu (2) ,ETFbitcoin (2) ,stwenhao (1)
How to get the full list of the elliptic curves, that could fit on N bits, based on secp256k1 used in Bitcoin? Now I can brute force some of the smaller ones, but I wonder, how to get some bigger values, and generate for example some 128-bit, 64-bit, or even 32-bit curves, without going through all points.

My current algorithm is something like that:
1. Pick some prime value "p".
2. Generate table of inverse values.
3. Starting from (1,1), find the nearest point, where y^2=x^3+7, and make it your base point.
4. Go through all points to calculate "n", it will be reached after trying to add (baseX,-baseY) to the (baseX,baseY).
5. Check if "n" is prime.
6. Make sure that "n" is different than "p".
7. Validate that if you pick "n" as the starting prime, and go through all steps, you will reach "p".
8. If there are many N-bit curves, pick the one where "p" is closest to 2^N-1, and "n<p".

After some bruteforcing, I reached those smaller curves. The question is: how to generate them faster, without going through all points, and reach the full list of elliptic curves, from 15-bit to 255-bit, based on secp256k1?
Code:
p=   79, n=   67, base=(1,  18)    7-bit
p=  967, n=  907, base=(1,  88)   10-bit
p= 1303, n= 1249, base=(1, 201)   11-bit
p= 3853, n= 3739, base=(3, 534)   12-bit
p= 7537, n= 7369, base=(1,3725)   13-bit
p=14071, n=13933, base=(1,3660)   14-bit