Exploring smaller elliptic curves y^2=x^3+7, derived from secp256k1

I'm trying to find out how to get a complete list of elliptic curves that fit within N bits, specifically those based on secp256k1 like the one used in Bitcoin. Right now, I can brute force some of the smaller ones, but I'm curious about how to generate larger values, like 128-bit, 64-bit, or even 32-bit curves, without having to check every single point. Here's what I've been doing: 1. Start with a prime value "p". 2. Create a table of inverse values. 3. From the point (1,1), find the closest point satisfying y^2=x^3+7, and use that as your base point. 4. Then, calculate "n" by trying to add (baseX, -baseY) to (baseX, baseY). 5. Check if "n" is prime. 6. Ensure that "n" is not equal to "p". 7. Validate that if you start with "n" as your prime and follow the steps, you should end up with "p". 8. If there are multiple N-bit curves, choose the one where "p" is nearest to 2^N-1 and "n < p". After some brute-forcing, I’ve managed to find these smaller curves. So I'm wondering: how can I speed up this process and generate a complete list of elliptic curves ranging from 15-bit to 255-bit based on secp256k1?

You didn't explain why you want these properties of 2 curves forming a 2-cycle. Is it just because this is the case for secp256k1, as noted for example (together with other interesting properties) in [1] ? [1] https://hackmd.io/@dJO3Nbl4RTirkR2uDM6eOA/Bk0NvC8Vo

it looks like the same what ecdsa123 has wrote in https://bitcointalk.org/index.php?topic=5453079.msg62280944#msg62280944

Don't do that. If for each prime "p" you are trying to generate the full table of all inverse values, from 1 to p-1, then this is one of your bottlenecks. Just use the extended Euclidean algorithm, and calculate all values on-the-fly, when they are needed. How do you find that point? If by brute force, then it could be optimized. For example, if you guess that x=1, then you need to calculate just sqrt(8), which means raising 8 to the power of 0.5. If you replace 0.5 by the right number, depending on "p", then you could do it faster than by checking every point. Also, when raising numbers to powers, you don't have to go through all of them, but you can use modular exponentiation algorithms. You don't have to go through all points. Imagine checking 115792089237316195423570985008687907852837564279074904382605163141518161494337 points in secp256k1. That means, your current program can only show you curves you can fully break. Better use Hasse's theorem. Even if you start from "p=n", and then jump between "p+value" and "p-value" for consecutive values, like 0, 1, 2, then you will get there much faster than by checking every point (but of course, for secp256k1, that would still mean checking around 2^128 possible values, so for bigger curves, you still have to implement Hasse's theorem properly, as mentioned in the previous link). How do you check if some number is prime? If you check every single number, odd or even, then it could be also optimized. For those 2-cycle curves, you can start from some odd prime, and check every sixth value, because in all cases you need only primes of the form "p=6k+1", and "n=6m+1". Also, you can check numbers only to the point, where the square is less or equal than your potential prime. For bigger curves like secp256k1, even that is not enough, and there are more estimations. For example, if you want to find 256-bit "p", then you pick a range between 2^256-2^32-2^10, and 2^256-2^32. Then, you find prime numbers only in this range, so you will get only a few possible values, where 115792089237316195423570985008687907853269984665640564039457584007908834671663 is the biggest prime, that is less than 2^256-2^32. The short answer is: you have to estimate more, and brute force less. For example, if you have "p" and "n" in secp256k1, then you don't have 100% guarantee that both values are prime. They probably are, but it is based on estimation, and not on some hard, mathematical proof, because that would require checking 2^128 values, and that would mean breaking the curve. If you want to make safe curves, and not break them at the same time, then you have to estimate things, not compute them exactly, for all cases, all points, all inverse values, etc.

The bitcoin cryptographic curve has two constants P and N. P is the number of points on the curve and N is the number of private keys on the curve. Naturally, P is larger than N, which means those points don't have private keys. OP is trying to find smaller values of P and N that work for this curve equation x^2 = y^3 + 7 used in Bitcoin, because it uses enormous P and N values. Prime factorization is your friend, and I'm sure all those people running Prime95 over the past 2 decades have a table of prime numbers stored somewhere (all less than 2^256).

can you explain : Naturally, P is larger than N, which means those points don't have private keys. if P is how much points are on curve, N -> max privkeys , so There are d=P-N , points without privatekeys? can you show that point?

There's a reason why you can't take an arbitrary public key and find the private key for it (let's assume you do not know the range at all), as the values are practically unknown. It just hit me, that those subset of P-N points have two distinct (R,s) pairs* when making a signature from that private key [well technically, they have twice that amount, but the other two are from taking the negative of S which is non-standard and not allowed by Bitcoin anyway]. So you since those points are generated extremely rarely and there are almost no instances of them in the wild, you can say, for practical purposes, that their private keys are virtually non-existent. *it all starts with the R value, which is calculated by R = G*x coord of the public key. So P-N of these keys have another public key point somewhere in secp256k1 that you can form by calculation but not necessarily from the standard EC point generation.

Definitely not. P is the range of acceptable values for (x,y) coordinates. If you have the simplest case, p=79, n=67, then it doesn't mean you have 79 points. That only means if you take any (x,y) point, then they all can be placed on a 79x79 square monochromatic bitmap, with (0,0) point in the top left corner, and all other points somewhere in the middle. He cannot, because there are no such points. For all of those smaller curves, listed by garlonicon, you can just compute all points, count them, and see that "n" properly reflects the number of points for any given "p". If you have p=79, and you start from any valid point, where y^2=x^3+7, then if you start incrementing it, you will reach only 67 points, not 79. You always start from some prime "p", and then you reach your "n" by checking that if you multiply it by your base point, then you will reach (0,0) as your result. Also note that if you picked some "p", then you cannot use some arbitrary "n". You should calculate it. For p=79, the only valid result is n=67. And for p=67, you will reach only n=79 (that also can show you, why P is not the number of points, as you cannot have 67 points with 79 private keys, and you can check that such elliptic curve is valid). The only reason for that is modulo bias, introduced by "r=(k*G).x", where x-value has range from 1 to p-1, but r-value should be between 1 and n-1. It is true for all curves, where p!=n. However, it doesn't mean we have less keys, it only means some of them will wrap around, exactly in the same way as any hash between "n" and 2^256 will be wrapped into the proper range, when you calculate your z-value, used in signatures. It is more difficult to handle other cases properly. Only for those pairs, you can safely assume, that h=1, exactly as in secp256k1. Of course, you can use for example "p=109, n=43, base=(2,48)", but then "h=1" is probably not the right choice.

I implemented some optimizations, and I can now get more values. Thank you all for your hints, more improvements are ongoing: Edit: Because I want to recreate the whole generation procedure for secp256k1. And to do that, I think it is important to learn things gradually, starting from the smallest elliptic curves, and then applying more and more optimizations, to finally reach the same results as in secp256k1. Yes, but by doing it in this way, it can also reveal the procedure for smaller elliptic curves, for example secp160k1, secp192k1, and secp224k1. It is also about solving the mystery behind the half of the base point: Few months ago, I thought x-value is some kind of hash, potentially having more than 160 bits (for example 192 bits). However, when I tried to implement everything by myself from scratch, I discovered more interesting things. For smaller values, the whole procedure of generating a curve does not involve hashing at all! It is not needed. It is described in PDFs, but if you want to generate any curve with certain properties, you don't have to implement any hash function. So, I wonder if that was the case in secp256k1. Maybe the creator didn't implement any hashing, and all values we can see, are just produced by taking modulo square roots, modulo cube roots, counting "n" based on "p", and things like that? Some example: you pick some "p", as in secp256k1. Then you calculate the only valid "n" for that "p". And then, if you observe the last 128 bits of "n", and take only that, then you cannot see, if it was some result of some 128-bit hash function or not. Then, by seeing only "baaedce6 af48a03b bfd25e8c d0364141" you could think "hey, someone just used 128-bit hash function here". But what if this was not the case? Another interesting thing is that according to PDFs, the base point is picked after calculating "n". However, in my code, it is now done the other way around: first I pick some base point, and then I can reach "n". So, I still have to learn, how it is possible to calculate "n" without touching any points (because if you touch some of them, then why not make it a base point? Unless the creator thought that picking x=1 was unsafe, and getting temporary points, and then discarding them, is needed anyway).

You seem to be interested in these stuff, so I thought maybe you could figure out which key belongs to the following public keys? And I just found out that if we multiply n/2 by 3 You will get half+1, or 0.5 plus 1 which is n/2+1 = 😉 Ps, G divided by 2 is not actually n/2, it just happens that since G is odd, aka 0x1 dividing it by 2 would divide n-1 by 2, I'm waiting to  see the secret behind G revealed, so chop chop crypto experts, and thanks.

I don't know. But those points seems to be generated, based on public key coordinates alone. And if this is true, then probably nobody knows the private key. After more optimizations, I noticed "p" and "n" values can be above or below some N-bit number. In this way, getting valid curves is faster, and it seems other curves were generated in a similar way, for example, for secp160k1, p-value is less than 2^160, but n-value is bigger: That means, to reproduce secp256k1 more accurately, I adjusted my code, to jump above and below 2^N, and reached those results: Edit: Wow, that was fast, I didn't expect it. After optimizing finding base point, and applying Hasse to find "n" based on "p", I quickly reached next curves:

Do you happen to have a script for EC operations where we could change p, n, and G?  Set target for +, - , *, /?

Up to 39-bit curves? Sure, but it is not yet public. For 40-bit curves and bigger? Not really, because it works on uint64, so you need uint128, uint256, or BigInteger implementation to cover that. But if you want some basic implementation, then you can cover small curves quite easily, because then you don't need any optimizations, and you can for example use brute force to calculate inversions, and it will work fine for the smallest ones.

Could u pls post script for calculate base point from P and N Thanks

You don't need "N" to do that. You only need "P". Of course, this is not the original algorithm. I simply start from x=1, and then reach the nearest point. But in secp256k1, and with many other curves, it was done in a different way. The small x-value is just a hint for me to explore point generation later, and to have some starting point, to calculate n-value, based on that. Also note, that in my code, I don't use n-value to calculate my base point. I can do that, based on p-value, and the curve equation, nothing else is needed to find any matching point. And then, by having that point, I use it to calculate n-value.

For fing G point from P or N, have u script ?

any point of orger G is same. N and P is a order of point G  and curve. Find base point for curvevand order is easy...

Tromp could u explain more what sort of coincidence you speak about on your link [1] This sage script doesn't find that it is rare to have the property of the post linked when P and N are primes...:

But the code I gave you is almost identical, if you want to use for example Sage Cell Server: Which means, you need more detailed version only if you want to implement each part from scratch. But that is also easy, for example if you want to implement "powermod", then this is a good starting point: https://en.wikipedia.org/wiki/Modular_exponentiation

Just to let you know: I created a list of 256-bit curves, with p-values, b-values, and n-values, as close to secp256k1, as I could. Also, in this case, secp160k1, secp192k1, and secp224k1 were reached with the same algorithm, so I hope it is correct. Feel free to grab it, and experiment with those curves: https://github.com/vjudeu/curves1000/blob/master/bits/bits256.txt Still trying to create a generator, but I guess it will take some time, to explore the algorithm, which was used in the standardized curves. Also note that there is some anomaly nearby 32-bit curve, because of Solinas primes, but I guess everything up to 64-bit curve will be broken fast anyway, so the rest of the list should be good enough. In the puzzle, people are working on 130-bit, so I guess this list could be useful for 128-bit and above, or maybe even 160-bit and above (because the challenge ends on 160-bit public key, which means, breaking the whole challenge will probably make secp160k1 obsolete).