3 ms·
Assuming that the results of this research paper are correct, it provides faster methods for determining whether a number is prime, for counting how many prime
by adrian_b 3y ago
Assuming that the results of this research paper are correct, it provides faster methods for determining whether a number is prime, for counting how many prime numbers exist in an interval and for finding all prime numbers within an interval.
This could accelerate the algorithms that depend on finding prime numbers, e.g. breaking by brute force RSA signatures or encryption.
- theamk 3y agoI did not fully verify the whole paper, but I feel pretty skeptical about usefullness of this for the small numbers. All of their formula provide a linear speed-up vs naive approach, which means that the big-O complexity is not going to be changing. So the best thing that this paper can do for determining if a number is a prime is to speed it up by some small constant factor (at most 210)... That's less than 8 bits of 2000+ bits that is currently used in RSA signatures, so basically noise.