6 ms·

Surprising hidden order unites prime numbers and crystal-like materials

157 points by foxes 8y ago

credit_guy 8y ago
Link to paper https://arxiv.org/abs/1802.10498 https://arxiv.org/abs/1802.10498 Also worth noting that Freeman Dyson pointed out the link between prime numbers, or the Riemann zeta function, and quasicrystals, see p. 2-3 of http://www.ams.org/notices/200902/rtx090200212p.pdf http://www.ams.org/notices/200902/rtx090200212p.pdf And here’s some marhoverflow discussions on Dyson’s ideas: https://mathoverflow.net/questions/133581/quasicrystals-and-the-riemann-hypothesis https://mathoverflow.net/questions/133581/quasicrystals-and-...
eganist 8y ago
Reminds me, whatever happened to the research into parallax compression? http://www.novaspivack.com/science/we-have-discovered-a-new-pattern-in-the-prime-numbers-parallax-compression http://www.novaspivack.com/science/we-have-discovered-a-new-...
oelmekki 8y ago
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?
- nl 8y ago
  No. It's the non-factorability of primes that is important.
  - gonzo 8y ago
    > It’s the non-factorability of primes that is important. Primes by definition have two, and only two factors. The difficulty of factoring a number which is the product of two large primes is the important bit.
    - toxik 8y ago
      I think the usual abstract algebra definition is one factor: itself. 1 is not considered a factor so that prime factorizations are unique, otherwise you could tack on an infinity of ones. Also Möbius becomes strange with infty factors.
      - ginnungagap 8y ago
        The abstract algebra definition is that p is a prime if whenever p divides a product ab then p divides at least one of a and b. Having no proper factors is the definition of an irreducible element. The two definitions agree for the integers and nice algebraic structure (UFDs) but there are algebraic structures in which they are not the same which explains why there are two differenr definitions and names in abstract algebra
  - rubyn00bie 8y ago
    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 :)
    - monocasa 8y ago
      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.
      - netsec_burn 8y ago
        Which are easier to generate with a prime formula..
        Timmah 8y ago
        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.
        nl 8y ago
        And it's wrong already. We already know all primes uses in encryption (just download a prime-number list).
        nl 8y ago
        This is wrong. We have lists of all primes used in crypto already. Just knowing them all doesn’t make attacks quicker.
- netsec_burn 8y ago
  Yes. If we can quickly generate large primes in a sequence then we can find the products easier.
  - throwawaymath 8y ago
    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 https://arxiv.org/pdf/1802.10498.pdf 2. https://en.wikipedia.org/wiki/Prime-counting_function https://en.wikipedia.org/wiki/Prime-counting_function
- throwawaymath 8y ago
  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.
AGoodName 8y ago
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 less obvious example. A small step further - all primes above 30 are of the form 30x+1, 30x+7, 30x+11, 30x+13, 30x+17, 30x+19, 30x+23 or 30x+29. Anything else is a multiple of 2,3 or 5. So above 30 only 8/30 numbers are worthy of being considered prime. See how we've created a new pattern for the multiple of 2x3x5 to rule out a swath of prime candidates.. I could repeat this each prime found. eg. I could take the common multiple of 2,3,5,7 (210) and create a similar pattern for all numbers above 210 that rules out the repeated multiples of 2,3,5 and 7. (leaving us just 58/210 numbers worthy of being considered prime). This is why you see peaks of primes at various repeating multiples. For every new prime found you can take the multiple of it and all previous primes. From that you can rule out primality for various offsets to any multiples of that number. So primes above certain numbers can only possibly exist in certain forms. Which is why you see primes at repeated patterns from each other - the primes can only exist in those forms.
- taneq 8y ago
  That seems so obvious when you put it like that. (Although I guess all of mathematics is either "obvious" or "unsolved".)
  - ipsin 8y ago
    I think most of what we've solved in math is not obvious. Some accessible examples would be Fermat's Last Theorem or the four color problem.
- deleted 8y ago
  [deleted]
- twanvl 8y ago
  Small correction: there are only 48 (not 58) numbers out of 210 that are not multiples of 2,3,5,7.
karmakaze 8y ago
I don't find it at all surprising that we find a natural occurrence of prime number patterns in nature. It makes perfect sense to find them in crystals if you think about it for a while. First remember that 'primeness' is not really a property of a number, it's the absence of the property of being composite. "Can only be divided..." meaning "Can't be divided..." meaning "Not composite." Second crystals are formed by repeating patterns. What happens if you compose a pattern from many repeating patterns and overlay them? There would be 'features' where the patterns don't overlap. Do papers try to make things seem difficult, exciting and mysterious on purpose?
- thaumasiotes 8y ago
  > First remember that 'primeness' is not really a property of a number, it's the absence of the property of being composite. What do you mean by this? What do you believe a "property" is? > Do papers try to make things seem difficult, exciting and mysterious on purpose? Yes, being surprising/exciting is a criterion for being published.
  - karmakaze 8y ago
    Certainly they could and are both (prime, composite) described as properties. The difference is that one can be described positively as 'having' and the other as 'not having' or 'having only'. If you've read Godel Escher Bach, it's very much in how it describes axiomatic space with 'foreground' vs 'background' when looking at the boundary of what's inside and outside a set of a given property. Compositeness is a construction. Primeness is what's outside. A sort of example from the book that plays in the "backgroumd': https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox
waynecochran 8y ago
No mention of whether this knowledge can be exploited to factor integers? You know where I’m going with this...

157 points by foxes 8y ago

Link to paper https://arxiv.org/abs/1802.10498 https://arxiv.org/abs/1802.10498 Also worth noting that Freeman Dyson pointed out the link between prime numbers, or the Riemann zeta function, and quasicrystals, see p. 2-3 of http://www.ams.org/notices/200902/rtx090200212p.pdf http://www.ams.org/notices/200902/rtx090200212p.pdf And here’s some marhoverflow discussions on Dyson’s ideas: https://mathoverflow.net/questions/133581/quasicrystals-and-the-riemann-hypothesis https://mathoverflow.net/questions/133581/quasicrystals-and-...

eganist 8y ago

Reminds me, whatever happened to the research into parallax compression? http://www.novaspivack.com/science/we-have-discovered-a-new-pattern-in-the-prime-numbers-parallax-compression http://www.novaspivack.com/science/we-have-discovered-a-new-...

oelmekki 8y ago

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?

nl 8y ago
No. It's the non-factorability of primes that is important.
- gonzo 8y ago
  > It’s the non-factorability of primes that is important. Primes by definition have two, and only two factors. The difficulty of factoring a number which is the product of two large primes is the important bit.
  - toxik 8y ago
    I think the usual abstract algebra definition is one factor: itself. 1 is not considered a factor so that prime factorizations are unique, otherwise you could tack on an infinity of ones. Also Möbius becomes strange with infty factors.
    - ginnungagap 8y ago
      The abstract algebra definition is that p is a prime if whenever p divides a product ab then p divides at least one of a and b. Having no proper factors is the definition of an irreducible element. The two definitions agree for the integers and nice algebraic structure (UFDs) but there are algebraic structures in which they are not the same which explains why there are two differenr definitions and names in abstract algebra
- rubyn00bie 8y ago
  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 :)
  - monocasa 8y ago
    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.
    - netsec_burn 8y ago
      Which are easier to generate with a prime formula..
      - Timmah 8y ago
        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.
        nl 8y ago
        And it's wrong already. We already know all primes uses in encryption (just download a prime-number list).
      - nl 8y ago
        This is wrong. We have lists of all primes used in crypto already. Just knowing them all doesn’t make attacks quicker.
netsec_burn 8y ago
Yes. If we can quickly generate large primes in a sequence then we can find the products easier.
- throwawaymath 8y ago
  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 https://arxiv.org/pdf/1802.10498.pdf 2. https://en.wikipedia.org/wiki/Prime-counting_function https://en.wikipedia.org/wiki/Prime-counting_function
throwawaymath 8y ago
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.

AGoodName 8y ago

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 less obvious example. A small step further - all primes above 30 are of the form 30x+1, 30x+7, 30x+11, 30x+13, 30x+17, 30x+19, 30x+23 or 30x+29. Anything else is a multiple of 2,3 or 5. So above 30 only 8/30 numbers are worthy of being considered prime. See how we've created a new pattern for the multiple of 2x3x5 to rule out a swath of prime candidates.. I could repeat this each prime found. eg. I could take the common multiple of 2,3,5,7 (210) and create a similar pattern for all numbers above 210 that rules out the repeated multiples of 2,3,5 and 7. (leaving us just 58/210 numbers worthy of being considered prime). This is why you see peaks of primes at various repeating multiples. For every new prime found you can take the multiple of it and all previous primes. From that you can rule out primality for various offsets to any multiples of that number. So primes above certain numbers can only possibly exist in certain forms. Which is why you see primes at repeated patterns from each other - the primes can only exist in those forms.

taneq 8y ago
That seems so obvious when you put it like that. (Although I guess all of mathematics is either "obvious" or "unsolved".)
- ipsin 8y ago
  I think most of what we've solved in math is not obvious. Some accessible examples would be Fermat's Last Theorem or the four color problem.
deleted 8y ago
[deleted]
twanvl 8y ago
Small correction: there are only 48 (not 58) numbers out of 210 that are not multiples of 2,3,5,7.

karmakaze 8y ago

I don't find it at all surprising that we find a natural occurrence of prime number patterns in nature. It makes perfect sense to find them in crystals if you think about it for a while. First remember that 'primeness' is not really a property of a number, it's the absence of the property of being composite. "Can only be divided..." meaning "Can't be divided..." meaning "Not composite." Second crystals are formed by repeating patterns. What happens if you compose a pattern from many repeating patterns and overlay them? There would be 'features' where the patterns don't overlap. Do papers try to make things seem difficult, exciting and mysterious on purpose?

thaumasiotes 8y ago
> First remember that 'primeness' is not really a property of a number, it's the absence of the property of being composite. What do you mean by this? What do you believe a "property" is? > Do papers try to make things seem difficult, exciting and mysterious on purpose? Yes, being surprising/exciting is a criterion for being published.
- karmakaze 8y ago
  Certainly they could and are both (prime, composite) described as properties. The difference is that one can be described positively as 'having' and the other as 'not having' or 'having only'. If you've read Godel Escher Bach, it's very much in how it describes axiomatic space with 'foreground' vs 'background' when looking at the boundary of what's inside and outside a set of a given property. Compositeness is a construction. Primeness is what's outside. A sort of example from the book that plays in the "backgroumd': https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox

waynecochran 8y ago

No mention of whether this knowledge can be exploited to factor integers? You know where I’m going with this...