Ask HN: If a pattern existed for Prime Numbers, would RSA et similar be secure? | Hacker News Reader

Ask HN: If a pattern existed for Prime Numbers, would RSA et similar be secure?

1 pointeezurr7 comments

It depends on how it was found, and what the pattern was, but broadly speaking, finding a pattern in the primes would probably not make factoring any easier, so RSA (and similar) would probably not be affected.

But the real question is - why do you ask? Is it because you think you've found a pattern, or is it because you are seeking to better understand how things work and how they are connected? There's value in asking the question you really have rather than making us guess.

I ask for both reasons. If there is a chance that this pattern could break RSA, I wouldn't be in a hurry to release it.

People are already looking to replace RSA because it will be broken in a post-quantum world. But my understanding is that and perceived pattern in where primes are won't help in finding factors of a number. Largely speaking we already know where primes are. Determining if a number is prime is in P, and identifying numbers as prime or not prime doesn't help break RSA.

If you've found a pattern, make sure you document clearly that you're the one who found it and then announce it as quickly as as widely as you can to let people verify that you're right, or find the flaws in your reasoning.

Alternatively, get someone you trust to verify it first, and then make it widely known.

What's more, if by some chance it did help break RSA, it's likely the three (and four) letter agencies already know it and are exploiting it already. By announcing it widely you would then be helping to push a world away from a system that's already broken without people knowing it.

Thanks for the feedback :)

Where would one go to release something like this? I don't have a university network to reach out to, nor do I have a network of mathematician friends. Should I create a PDF and post on ArXiv?

If you create a PDF and post on ArXiv, then tell me then I can post links to it on various math forums. You can make an account on mathstodon.xyz and post it there, post it on Twitter and tag a few mathematicians.

Or email me - address is in my profile.

As a quick sanity check, how have you checked it? I can possibly help with making it an accessible draft rather than trying to make it an academic paper. Being clear and engaging can be hard, but it's worth making the explanation readable rather than scholarly.

For reference, I'm going off-line now for about 12 hours, but I'll respond when I can. Take your time.

As it turns out, I created a slight variant of Wheel factorization. Surprisingly this did not up in any of the prime number/number theory articles I came across.

There is no shame in rediscovering an existing technique. It shows your thinking is sound. And you're right, that method is often glossed over as if unimportant, but the ideas resurface later in other sieving methods.

Even so, of you have a variant I would be interested in seeing it. Would you email it to me? Address in my profile.

Reply on news.ycombinator.com