Live data from Hacker News

Surprising hidden order unites prime numbers and crystal-like materials

phys.org

11–20 of 41 posts

Re: Surprising hidden order unites prime numbers and crystal-like materials

#11

A brief explanation of why primes peak at repeated multiples from a layman who's wondered why before. Obvious first example all primes above 2 are of the form 2x+1. An obvious repeating pattern of primes. You can take this a small step further. All primes above 6 are of the form 6x+1 or 6x+5. Anything else is a multiple of 2 or 3. Above 6 only 1/3 of numbers are worthy of being considered prime. This is a slightly le…

That seems so obvious when you put it like that. (Although I guess all of mathematics is either "obvious" or "unsolved".)

Re: Surprising hidden order unites prime numbers and crystal-like materials

#12

A brief explanation of why primes peak at repeated multiples from a layman who's wondered why before. Obvious first example all primes above 2 are of the form 2x+1. An obvious repeating pattern of primes. You can take this a small step further. All primes above 6 are of the form 6x+1 or 6x+5. Anything else is a multiple of 2 or 3. Above 6 only 1/3 of numbers are worthy of being considered prime. This is a slightly le…

[deleted]

Re: Surprising hidden order unites prime numbers and crystal-like materials

#13

A brief explanation of why primes peak at repeated multiples from a layman who's wondered why before. Obvious first example all primes above 2 are of the form 2x+1. An obvious repeating pattern of primes. You can take this a small step further. All primes above 6 are of the form 6x+1 or 6x+5. Anything else is a multiple of 2 or 3. Above 6 only 1/3 of numbers are worthy of being considered prime. This is a slightly le…

This pattern forms the basis for wheel factorization [1], a faster way to factor a number than naïve trial division.

[1] https://en.wikipedia.org/wiki/Wheel_factorization

Re: Surprising hidden order unites prime numbers and crystal-like materials

#14
post #9

Earlier quoted context omitted.

Pardon my extreme ignorance of the subject, but could you elaborate on why your statement is mutually exclusive of the OP? Not at all combative, just a sincerely interested layman :)

It doesn't matter to the algorithm that we know if it's a product of two primes. Anyone attacking an RSA private key knows that it is. The only unknown is which two primes.

Which are easier to generate with a prime formula..

Re: Surprising hidden order unites prime numbers and crystal-like materials

#15
post #4

I read once that prime numbers were a key element element on cryptography (because it's easy to multiply two prime numbers, but difficult to say if a number is a multiple of two prime numbers, if I remember correctly). Will this discovery have negative impact on it?

Yes. If we can quickly generate large primes in a sequence then we can find the products easier.

Re: Surprising hidden order unites prime numbers and crystal-like materials

#16

A brief explanation of why primes peak at repeated multiples from a layman who's wondered why before. Obvious first example all primes above 2 are of the form 2x+1. An obvious repeating pattern of primes. You can take this a small step further. All primes above 6 are of the form 6x+1 or 6x+5. Anything else is a multiple of 2 or 3. Above 6 only 1/3 of numbers are worthy of being considered prime. This is a slightly le…

Small correction: there are only 48 (not 58) numbers out of 210 that are not multiples of 2,3,5,7.

Re: Surprising hidden order unites prime numbers and crystal-like materials

#17
post #4

I read once that prime numbers were a key element element on cryptography (because it's easy to multiply two prime numbers, but difficult to say if a number is a multiple of two prime numbers, if I remember correctly). Will this discovery have negative impact on it?

No it won't. This result is related to the problems of proving properties about the prime numbers (such as gaps) and of determining whether or not a given number is prime. It has nothing to do with the computational intractability of factoring large numbers.

RSA utilizes an extremely large semiprime (the product of two very large prime numbers) to generate a public/private key pair. This result does not meaningfully change anything related to the computational work required to factor semiprime numbers that have over 600 digits.

Re: Surprising hidden order unites prime numbers and crystal-like materials

#18

A brief explanation of why primes peak at repeated multiples from a layman who's wondered why before. Obvious first example all primes above 2 are of the form 2x+1. An obvious repeating pattern of primes. You can take this a small step further. All primes above 6 are of the form 6x+1 or 6x+5. Anything else is a multiple of 2 or 3. Above 6 only 1/3 of numbers are worthy of being considered prime. This is a slightly le…

I haven't done all the math for this (I've deeply investigated the pattern for 2x+1) but it seems like this would be an obvious and intuitive result of primes. You are still generating primes from primes. Yes, you find more primes, but the computation is still dependent on primes. I'm still of the opinion that there is no complete pattern to the primes.

I'm assuming the researchers do not have the intent of confusing a crystal lattice structure with an actual mathematical lattice, because while they possibly may share similar influences in their models, one is math, the other is physics.

#keepmathpure

Re: Surprising hidden order unites prime numbers and crystal-like materials

#19
post #4

I read once that prime numbers were a key element element on cryptography (because it's easy to multiply two prime numbers, but difficult to say if a number is a multiple of two prime numbers, if I remember correctly). Will this discovery have negative impact on it?

Yes. If we can quickly generate large primes in a sequence then we can find the products easier.

You should read the paper authors' paper directly; a preprint version if available on arXiv.[1]

The authors don't provide a complexity analysis of their algorithm; in lieu of attempting to derive that analysis myself, I'm deeply skeptical that their algorithm can find arbitrarily large prime numbers in sub-exponential time; let alone the polynomial time needed for breaking classical public-key cryptography. The absence of such a complexity analysis is conspicuous because such an analysis would be groundbreaking.

However, I don't need to lean on the conspicuous absence of a proof of polynomial time complexity for their algorithm because their algorithm has explicit limitations. It's an approximation method (albeit with high accuracy) that can only find primes located in dyadic intervals having many Braggs peaks and a relatively small left endpoint. In the paper they represent this interval with (M, M + L); in general a dyadic interval is an interval of the form (k/2n, k+1/2n) which may be either open or closed.

In other words the algorithm has costly limitations, no proof of polynomial time complexity and the authors don't even study its behavior for a left endpoint greater than 10^6. RSA semiprime numbers have 600 digits - this result isn't even in the same galaxy. Considering the explicit limitations in the authors' paper and the lack of interesting analysis indicating otherwise, it's likely that the problem of finding a suitable dyadic interval containing a large semiprime number's factors will just reduce to the problem of finding its factors anyway.

For what it's worth, this is all distinct from a more conceptual problem that undermines any use this result could have for cryptanalysis. Take a look at the prime counting function.[2] Per the prime counting function, there are approximately 2.53274 × 10^305 primes and 2.27654 × 10^613 primes less than 2^1024 and 2^2048, respectively. It's physically impossible to construct a lookup table consisting of all products of all pairs of primes in either set because there isn't enough matter in the universe to contain the information. But even if there was, you would never feasibly pick out the correct semiprime number corresponding to a given RSA private key by doing lookups in this way.

_______________________________________

1. https://arxiv.org/pdf/1802.10498.pdf

2. https://en.wikipedia.org/wiki/Prime-counting_function

Re: Surprising hidden order unites prime numbers and crystal-like materials

#20
post #9

Earlier quoted context omitted.

It doesn't matter to the algorithm that we know if it's a product of two primes. Anyone attacking an RSA private key knows that it is. The only unknown is which two primes.

Which are easier to generate with a prime formula..

Define "easier" in this context. If you have an algorithm whose complexity increases exponentially with the key length, saying you made a 10% gain doesn't mean squat.
Post reply on HN