Elliptic curve as a product of 3 cyclic groups possible?












2












$begingroup$


I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)



So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)



I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$



It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?



Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.










share|improve this question









New contributor




J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    2












    $begingroup$


    I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
    (btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)



    So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)



    I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$



    It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
    I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?



    Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
    Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.










    share|improve this question









    New contributor




    J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      2












      2








      2





      $begingroup$


      I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
      (btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)



      So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)



      I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$



      It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
      I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?



      Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
      Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.










      share|improve this question









      New contributor




      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
      (btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)



      So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)



      I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$



      It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
      I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?



      Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
      Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.







      elliptic-curves






      share|improve this question









      New contributor




      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 8 hours ago









      kelalaka

      6,36522142




      6,36522142






      New contributor




      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 8 hours ago









      J. DoeJ. Doe

      132




      132




      New contributor




      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      J. Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          1 Answer
          1






          active

          oldest

          votes


















          4












          $begingroup$

          Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.



          For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.



          It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
          $$ uP = ((qr)^{-1} bmod p)(qrT) $$
          but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.



          Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
          $$ 4e - (e+1-n)^2 = 3g^2 $$
          then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.



          In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.






          share|improve this answer









          $endgroup$













          • $begingroup$
            So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
            $endgroup$
            – J. Doe
            6 hours ago












          • $begingroup$
            Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
            $endgroup$
            – J. Doe
            5 hours ago











          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: "281"
          };
          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: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          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
          });


          }
          });






          J. Doe is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66597%2felliptic-curve-as-a-product-of-3-cyclic-groups-possible%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









          4












          $begingroup$

          Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.



          For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.



          It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
          $$ uP = ((qr)^{-1} bmod p)(qrT) $$
          but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.



          Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
          $$ 4e - (e+1-n)^2 = 3g^2 $$
          then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.



          In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.






          share|improve this answer









          $endgroup$













          • $begingroup$
            So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
            $endgroup$
            – J. Doe
            6 hours ago












          • $begingroup$
            Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
            $endgroup$
            – J. Doe
            5 hours ago
















          4












          $begingroup$

          Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.



          For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.



          It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
          $$ uP = ((qr)^{-1} bmod p)(qrT) $$
          but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.



          Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
          $$ 4e - (e+1-n)^2 = 3g^2 $$
          then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.



          In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.






          share|improve this answer









          $endgroup$













          • $begingroup$
            So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
            $endgroup$
            – J. Doe
            6 hours ago












          • $begingroup$
            Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
            $endgroup$
            – J. Doe
            5 hours ago














          4












          4








          4





          $begingroup$

          Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.



          For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.



          It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
          $$ uP = ((qr)^{-1} bmod p)(qrT) $$
          but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.



          Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
          $$ 4e - (e+1-n)^2 = 3g^2 $$
          then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.



          In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.






          share|improve this answer









          $endgroup$



          Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.



          For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.



          It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
          $$ uP = ((qr)^{-1} bmod p)(qrT) $$
          but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.



          Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
          $$ 4e - (e+1-n)^2 = 3g^2 $$
          then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.



          In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 7 hours ago









          Thomas PorninThomas Pornin

          69.2k13183262




          69.2k13183262












          • $begingroup$
            So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
            $endgroup$
            – J. Doe
            6 hours ago












          • $begingroup$
            Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
            $endgroup$
            – J. Doe
            5 hours ago


















          • $begingroup$
            So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
            $endgroup$
            – J. Doe
            6 hours ago












          • $begingroup$
            Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
            $endgroup$
            – J. Doe
            5 hours ago
















          $begingroup$
          So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
          $endgroup$
          – J. Doe
          6 hours ago






          $begingroup$
          So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
          $endgroup$
          – J. Doe
          6 hours ago














          $begingroup$
          Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
          $endgroup$
          – J. Doe
          5 hours ago




          $begingroup$
          Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
          $endgroup$
          – J. Doe
          5 hours ago










          J. Doe is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          J. Doe is a new contributor. Be nice, and check out our Code of Conduct.













          J. Doe is a new contributor. Be nice, and check out our Code of Conduct.












          J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
















          Thanks for contributing an answer to Cryptography 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%2fcrypto.stackexchange.com%2fquestions%2f66597%2felliptic-curve-as-a-product-of-3-cyclic-groups-possible%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

          Сан-Квентин

          8-я гвардейская общевойсковая армия

          Алькесар