5 ms·

Elliptic Curves

122 points by CarolineW 9y ago

ice109 9y ago
the profusion of posted slides on the internet is a detriment to researchers everywhere. so many times i've googled something technical (CS, math, engineering) and what percolates to the top are lecture slides, which are almost useless for actual in depth learning. edit: spoke too soon - only the first link is slides.
- stablemap 9y ago
  It believe mathematicians will continue to favor boards. Sitting in the audience I greatly prefer this; however, such lectures have less chance of being posted at all. For this topic we are lucky to have Silverman's book [1], which everyone seems to like. [1] https://www.math.brown.edu/~jhs/AECHome.html https://www.math.brown.edu/~jhs/AECHome.html
  - ice109 9y ago
    can you explain to me why an elliptic curve over C is a quotient manifold (like the torus on page 7 of the first set of slides)?
    - yequalsx 9y ago
      The explanation is in lecture 15. It requires knowledge of some advanced mathematics. Abelian varieties over the complex numbers are analytically isomorphic to a torus.
    - stablemap 9y ago
      I would expect him to spell this out in lectures 15 and 16. It does take work. What is surprising is that despite their all looking the same -- certainly they are the same as real manifolds -- there are tons of elliptic curves. The difference is in the complex analytic structure.
      - williamstein 9y ago
        They (the space of complex points on any elliptic curve over C) are the same (homeomorphic) as topological spaces. However, they are not the same as complex analytic manifolds, which is a stronger condition (requiring an analytic isomorphism, not just a topological one).
        stablemap 9y ago
        I should have said real manifolds; I thought that was what the parent comment had in mind but the brevity wasn't worth it. Of course, I've learned a lot about these things from your writings.
    - xyzzyz 9y ago
      It is explained in a relatively elementary way in Frances Kirwan's "Complex Algebraic Curves"[1]. The book is pretty self contained, and much more entry level than, say, Silverman. [1] - https://www.amazon.com/Complex-Algebraic-Mathematical-Society-Student/dp/0521423538 https://www.amazon.com/Complex-Algebraic-Mathematical-Societ...
    - deleted 9y ago
      [deleted]
- zitterbewegung 9y ago
  When I was doing research projects for my undergraduate degree we primarily used the web differently. 0. First thing we would search is the Arxiv front end http://front.math.ucdavis.edu/ http://front.math.ucdavis.edu/ . Usually we would have a researcher in mind. If we didn't then we would look at Wikipedia. 1. We would use wikipedia to get general knowledge and information about the topic. Sometimes lecture notes and presentations would be looked at too but we would eventually get to papers. 2. If the topic was relevant after getting the gist we would look at the citations on wikipedia and track down authors. 3. Books we would obtain electronically. Papers would be tracked down on Arxiv. 4. Rinse and repeat if you didn't understand a topic that was cited in any of the other steps.
lukejduncan 9y ago
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
- baobrien 9y ago
  Elliptic Curves are one of the core mathematical constructs behind most of the commonly used non-RSA asymmetric cryptographic algorithms (curve25519, ed25519, ECDH, ECDSA).
  - v64 9y ago
    But is there a particular reason like a news event that they're trending right now?
    - sillysaurus3 9y ago
      Randomness doing its usual.
    - kobeya 9y ago
      Bitcoin uses them.
- ColinWright 9y ago
  Ignoring many important details ... Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0]. A group is a set of things, and a binary operation that satisfies certain rules. At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-Hellman-Merkle-Williamson, or in factoring via Pollard P-1, use the fact that the numbers we are using are an example of a group. The groups being used are usually: * For DHMW, the integers modulo a large prime, or * For RSA, the integers that are co-prime to the product of two large primes. In each case the operation is multiplication modulo something. So then we can ask if the same algorithms work if we use a different group instead, and whether the result will have better or worse characteristics. The answers to that are (1) yes, the algorithms work in other groups, and (2) it depends on the particular group or groups used. So given an elliptic curve, it turns out that the points can form a group if we define a particular operation[1]. Then it turns out that the rational points form a group. Then we can convert that to work modulo a prime, and we end up with a finite group. And that's exactly what we need to use some of our algorithms. The question of whether this group is better depends, and is too long to fit in a single HN comment, but the main point is that there are many possible elliptic curves to choose from, and many possible primes to use, and so we have more choice. That alone makes it worth considering. But the answer turns out to be yes, some of the algorithms have better characteristics on these new groups. For example, using elliptic curves we can use smaller keys for RSA or DHMW, and the elliptic curve version of Pollard P-1 is now the third fastest known factoring algorithm, and probably fastest over a certain range of sizes. I would be happy to answer any questions, either here or by email. [0] https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Group_(mathematics) [1] And augment the points, and avoid certain pathological curves

122 points by CarolineW 9y ago

the profusion of posted slides on the internet is a detriment to researchers everywhere. so many times i've googled something technical (CS, math, engineering) and what percolates to the top are lecture slides, which are almost useless for actual in depth learning. edit: spoke too soon - only the first link is slides.

stablemap 9y ago
It believe mathematicians will continue to favor boards. Sitting in the audience I greatly prefer this; however, such lectures have less chance of being posted at all. For this topic we are lucky to have Silverman's book [1], which everyone seems to like. [1] https://www.math.brown.edu/~jhs/AECHome.html https://www.math.brown.edu/~jhs/AECHome.html
- ice109 9y ago
  can you explain to me why an elliptic curve over C is a quotient manifold (like the torus on page 7 of the first set of slides)?
  - yequalsx 9y ago
    The explanation is in lecture 15. It requires knowledge of some advanced mathematics. Abelian varieties over the complex numbers are analytically isomorphic to a torus.
  - stablemap 9y ago
    I would expect him to spell this out in lectures 15 and 16. It does take work. What is surprising is that despite their all looking the same -- certainly they are the same as real manifolds -- there are tons of elliptic curves. The difference is in the complex analytic structure.
    - williamstein 9y ago
      They (the space of complex points on any elliptic curve over C) are the same (homeomorphic) as topological spaces. However, they are not the same as complex analytic manifolds, which is a stronger condition (requiring an analytic isomorphism, not just a topological one).
      - stablemap 9y ago
        I should have said real manifolds; I thought that was what the parent comment had in mind but the brevity wasn't worth it. Of course, I've learned a lot about these things from your writings.
  - xyzzyz 9y ago
    It is explained in a relatively elementary way in Frances Kirwan's "Complex Algebraic Curves"[1]. The book is pretty self contained, and much more entry level than, say, Silverman. [1] - https://www.amazon.com/Complex-Algebraic-Mathematical-Society-Student/dp/0521423538 https://www.amazon.com/Complex-Algebraic-Mathematical-Societ...
  - deleted 9y ago
    [deleted]
zitterbewegung 9y ago
When I was doing research projects for my undergraduate degree we primarily used the web differently. 0. First thing we would search is the Arxiv front end http://front.math.ucdavis.edu/ http://front.math.ucdavis.edu/ . Usually we would have a researcher in mind. If we didn't then we would look at Wikipedia. 1. We would use wikipedia to get general knowledge and information about the topic. Sometimes lecture notes and presentations would be looked at too but we would eventually get to papers. 2. If the topic was relevant after getting the gist we would look at the citations on wikipedia and track down authors. 3. Books we would obtain electronically. Papers would be tracked down on Arxiv. 4. Rinse and repeat if you didn't understand a topic that was cited in any of the other steps.

lukejduncan 9y ago

I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?

baobrien 9y ago
Elliptic Curves are one of the core mathematical constructs behind most of the commonly used non-RSA asymmetric cryptographic algorithms (curve25519, ed25519, ECDH, ECDSA).
- v64 9y ago
  But is there a particular reason like a news event that they're trending right now?
  - sillysaurus3 9y ago
    Randomness doing its usual.
  - kobeya 9y ago
    Bitcoin uses them.
ColinWright 9y ago
Ignoring many important details ... Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0]. A group is a set of things, and a binary operation that satisfies certain rules. At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-Hellman-Merkle-Williamson, or in factoring via Pollard P-1, use the fact that the numbers we are using are an example of a group. The groups being used are usually: * For DHMW, the integers modulo a large prime, or * For RSA, the integers that are co-prime to the product of two large primes. In each case the operation is multiplication modulo something. So then we can ask if the same algorithms work if we use a different group instead, and whether the result will have better or worse characteristics. The answers to that are (1) yes, the algorithms work in other groups, and (2) it depends on the particular group or groups used. So given an elliptic curve, it turns out that the points can form a group if we define a particular operation[1]. Then it turns out that the rational points form a group. Then we can convert that to work modulo a prime, and we end up with a finite group. And that's exactly what we need to use some of our algorithms. The question of whether this group is better depends, and is too long to fit in a single HN comment, but the main point is that there are many possible elliptic curves to choose from, and many possible primes to use, and so we have more choice. That alone makes it worth considering. But the answer turns out to be yes, some of the algorithms have better characteristics on these new groups. For example, using elliptic curves we can use smaller keys for RSA or DHMW, and the elliptic curve version of Pollard P-1 is now the third fastest known factoring algorithm, and probably fastest over a certain range of sizes. I would be happy to answer any questions, either here or by email. [0] https://en.wikipedia.org/wiki/Group_(mathematics) https://en.wikipedia.org/wiki/Group_(mathematics) [1] And augment the points, and avoid certain pathological curves