Quote
2. Generate table of inverse values.
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.Quote
3. Starting from (1,1), find the nearest point, where y^2=x^3+7, and make it your base point.
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.Quote
4. Go through all points to calculate "n", it will be reached after trying to add (baseX,-baseY) to the (baseX,baseY).
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).Quote
5. Check if "n" is prime.
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.Quote
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?
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. 