Why are elliptic curves important for elementary number theory?












16












$begingroup$


Elliptic curves (or even Abelian varieties) are useful tools for many high-falutin' reasons




  1. They can be used to construct $ell$-adic Galois representations

  2. One can find automorphic forms from an elliptic curve fairly easily

  3. There is a nice way to find formal group laws using elliptic curves

  4. Families of elliptic curves provide nice geometric examples for various cohomological phenomena


But, I have yet to learn why they they are important from an elementary number-theoretic perspective. Why did early mathematicians "run into" elliptic curves and abelian varieties to begin with and how are they useful for elementary number theory?










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
    $endgroup$
    – bertram
    Jun 1 '17 at 20:36












  • $begingroup$
    From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
    $endgroup$
    – 54321user
    Dec 5 '17 at 0:34










  • $begingroup$
    Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
    $endgroup$
    – Ethan Bolker
    Apr 15 '18 at 20:17
















16












$begingroup$


Elliptic curves (or even Abelian varieties) are useful tools for many high-falutin' reasons




  1. They can be used to construct $ell$-adic Galois representations

  2. One can find automorphic forms from an elliptic curve fairly easily

  3. There is a nice way to find formal group laws using elliptic curves

  4. Families of elliptic curves provide nice geometric examples for various cohomological phenomena


But, I have yet to learn why they they are important from an elementary number-theoretic perspective. Why did early mathematicians "run into" elliptic curves and abelian varieties to begin with and how are they useful for elementary number theory?










share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
    $endgroup$
    – bertram
    Jun 1 '17 at 20:36












  • $begingroup$
    From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
    $endgroup$
    – 54321user
    Dec 5 '17 at 0:34










  • $begingroup$
    Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
    $endgroup$
    – Ethan Bolker
    Apr 15 '18 at 20:17














16












16








16


7



$begingroup$


Elliptic curves (or even Abelian varieties) are useful tools for many high-falutin' reasons




  1. They can be used to construct $ell$-adic Galois representations

  2. One can find automorphic forms from an elliptic curve fairly easily

  3. There is a nice way to find formal group laws using elliptic curves

  4. Families of elliptic curves provide nice geometric examples for various cohomological phenomena


But, I have yet to learn why they they are important from an elementary number-theoretic perspective. Why did early mathematicians "run into" elliptic curves and abelian varieties to begin with and how are they useful for elementary number theory?










share|cite|improve this question











$endgroup$




Elliptic curves (or even Abelian varieties) are useful tools for many high-falutin' reasons




  1. They can be used to construct $ell$-adic Galois representations

  2. One can find automorphic forms from an elliptic curve fairly easily

  3. There is a nice way to find formal group laws using elliptic curves

  4. Families of elliptic curves provide nice geometric examples for various cohomological phenomena


But, I have yet to learn why they they are important from an elementary number-theoretic perspective. Why did early mathematicians "run into" elliptic curves and abelian varieties to begin with and how are they useful for elementary number theory?







number-theory elementary-number-theory elliptic-curves abelian-varieties






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited May 28 '17 at 3:04









tilper

12.9k11145




12.9k11145










asked May 28 '17 at 3:01









54321user54321user

1,288622




1,288622








  • 2




    $begingroup$
    The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
    $endgroup$
    – bertram
    Jun 1 '17 at 20:36












  • $begingroup$
    From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
    $endgroup$
    – 54321user
    Dec 5 '17 at 0:34










  • $begingroup$
    Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
    $endgroup$
    – Ethan Bolker
    Apr 15 '18 at 20:17














  • 2




    $begingroup$
    The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
    $endgroup$
    – bertram
    Jun 1 '17 at 20:36












  • $begingroup$
    From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
    $endgroup$
    – 54321user
    Dec 5 '17 at 0:34










  • $begingroup$
    Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
    $endgroup$
    – Ethan Bolker
    Apr 15 '18 at 20:17








2




2




$begingroup$
The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
$endgroup$
– bertram
Jun 1 '17 at 20:36






$begingroup$
The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website!
$endgroup$
– bertram
Jun 1 '17 at 20:36














$begingroup$
From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
$endgroup$
– 54321user
Dec 5 '17 at 0:34




$begingroup$
From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...)
$endgroup$
– 54321user
Dec 5 '17 at 0:34












$begingroup$
Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
$endgroup$
– Ethan Bolker
Apr 15 '18 at 20:17




$begingroup$
Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that.
$endgroup$
– Ethan Bolker
Apr 15 '18 at 20:17










1 Answer
1






active

oldest

votes


















8












$begingroup$

I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.



At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.



As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:




  • Choose a number $n in mathbb{N}$ to be factored.

  • Choose a random elliptic curve $E(mathbb{Z}_n)$ and a point $P in E$.

  • Choose a smooth number $e in mathbb{N}$. $m!$ for a small $m$ is a common choice.


  • Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:




    • All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.


    • We arrive at $kP = infty$ for some $k leq e$. If this happens, go to the second bullet above and repeat.


    • We arrive at an addition that could not be computed because the inverse of an element $k in mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.





Read more about why this works.



Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $mathbb{Z}_p$ setting.






share|cite|improve this answer











$endgroup$














    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2299604%2fwhy-are-elliptic-curves-important-for-elementary-number-theory%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    8












    $begingroup$

    I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.



    At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.



    As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:




    • Choose a number $n in mathbb{N}$ to be factored.

    • Choose a random elliptic curve $E(mathbb{Z}_n)$ and a point $P in E$.

    • Choose a smooth number $e in mathbb{N}$. $m!$ for a small $m$ is a common choice.


    • Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:




      • All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.


      • We arrive at $kP = infty$ for some $k leq e$. If this happens, go to the second bullet above and repeat.


      • We arrive at an addition that could not be computed because the inverse of an element $k in mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.





    Read more about why this works.



    Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $mathbb{Z}_p$ setting.






    share|cite|improve this answer











    $endgroup$


















      8












      $begingroup$

      I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.



      At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.



      As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:




      • Choose a number $n in mathbb{N}$ to be factored.

      • Choose a random elliptic curve $E(mathbb{Z}_n)$ and a point $P in E$.

      • Choose a smooth number $e in mathbb{N}$. $m!$ for a small $m$ is a common choice.


      • Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:




        • All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.


        • We arrive at $kP = infty$ for some $k leq e$. If this happens, go to the second bullet above and repeat.


        • We arrive at an addition that could not be computed because the inverse of an element $k in mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.





      Read more about why this works.



      Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $mathbb{Z}_p$ setting.






      share|cite|improve this answer











      $endgroup$
















        8












        8








        8





        $begingroup$

        I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.



        At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.



        As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:




        • Choose a number $n in mathbb{N}$ to be factored.

        • Choose a random elliptic curve $E(mathbb{Z}_n)$ and a point $P in E$.

        • Choose a smooth number $e in mathbb{N}$. $m!$ for a small $m$ is a common choice.


        • Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:




          • All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.


          • We arrive at $kP = infty$ for some $k leq e$. If this happens, go to the second bullet above and repeat.


          • We arrive at an addition that could not be computed because the inverse of an element $k in mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.





        Read more about why this works.



        Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $mathbb{Z}_p$ setting.






        share|cite|improve this answer











        $endgroup$



        I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.



        At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.



        As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:




        • Choose a number $n in mathbb{N}$ to be factored.

        • Choose a random elliptic curve $E(mathbb{Z}_n)$ and a point $P in E$.

        • Choose a smooth number $e in mathbb{N}$. $m!$ for a small $m$ is a common choice.


        • Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:




          • All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.


          • We arrive at $kP = infty$ for some $k leq e$. If this happens, go to the second bullet above and repeat.


          • We arrive at an addition that could not be computed because the inverse of an element $k in mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.





        Read more about why this works.



        Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $mathbb{Z}_p$ setting.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Apr 15 '18 at 20:09

























        answered May 28 '17 at 5:09









        Kaj HansenKaj Hansen

        27.8k43980




        27.8k43980






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2299604%2fwhy-are-elliptic-curves-important-for-elementary-number-theory%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            android studio warns about leanback feature tag usage required on manifest while using Unity exported app?

            SQL update select statement

            WPF add header to Image with URL pettitions [duplicate]