3 ms·

This is a little bit of a layman's question but maybe someone is interested: When people go searching for prime numbers / bitcoin with massive compute, I assum

This is a little bit of a layman's question but maybe someone is interested: When people go searching for prime numbers / bitcoin with massive compute, I assume that there are huge libraries of "shortcuts" to reduce the searching space, like prime numbers only appear with certain patterns, or there are large "holes" in the number space that do not need to be searched, etc. (see videos e.g. about how prime numbers make spirals on the polar coord. system, etc). I.e. if you know these you can accelerate/reduce your search cost by orders of magnitude. For whatever various encryption algorithm that people choose to test or attack (like this story), is there somewhere such libraries of "shortcuts" are kept and well known? To reduce the brute force search need? And is the state of sharing these to the point that the encryption services are designed to avoid the shortcut vulnerabilities? Was always wondering this.

tomesco 2y ago
There exist certain classes of prime numbers that should not be used for some cryptographic operations because algorithms exist that reduce the computation required for factoring attacks. This more often applies to cases where smaller primes are applied. Sources for this king of knowledge are mathematics or cryptography textbooks. For other cryptographic operations, almost any sufficiently large prime can be used. Even a 50% reduction on a computation that will take trillions of years, has no practical impact.
cryptizard 2y ago
That's not really how it works. There aren't any noticeable patterns in prime numbers (besides trivial ones like they are all odd numbers) and they remain dense (no big gaps) even for very large numbers like what are used in RSA. The best algorithm for generating prime numbers is to just pick a really big random odd number and then test if it is prime, repeat until you find one. Now, factoring large numbers is a separate thing. You don't brute force all the possible factors, that would be a really bad approach. Modern algorithms are called "sieves," this is a gross oversimplification but essentially they keep picking random numbers and computing relations between them until they come up with enough that have a certain property that you can combine them together to find one of the factors. It doesn't have anything to do with shortcuts or patterns or tricks, it is just a fundamental number theory algorithm.

tomesco 2y ago

There exist certain classes of prime numbers that should not be used for some cryptographic operations because algorithms exist that reduce the computation required for factoring attacks. This more often applies to cases where smaller primes are applied. Sources for this king of knowledge are mathematics or cryptography textbooks. For other cryptographic operations, almost any sufficiently large prime can be used. Even a 50% reduction on a computation that will take trillions of years, has no practical impact.

cryptizard 2y ago

That's not really how it works. There aren't any noticeable patterns in prime numbers (besides trivial ones like they are all odd numbers) and they remain dense (no big gaps) even for very large numbers like what are used in RSA. The best algorithm for generating prime numbers is to just pick a really big random odd number and then test if it is prime, repeat until you find one. Now, factoring large numbers is a separate thing. You don't brute force all the possible factors, that would be a really bad approach. Modern algorithms are called "sieves," this is a gross oversimplification but essentially they keep picking random numbers and computing relations between them until they come up with enough that have a certain property that you can combine them together to find one of the factors. It doesn't have anything to do with shortcuts or patterns or tricks, it is just a fundamental number theory algorithm.