Why was the term “discrete” used in discrete logarithm? Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Trying to better understand the failure of the Index Calculus for ECDLPWhat is so special about elliptic curves?Why is the discrete logarithm problem assumed to be hard?What is the difference between discrete logarithm and logarithm?Calculating the discrete logarithmWhy is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?How to construct a hash function into a cyclic group such that its discrete log is intractable?Discrete logarithm key sizes for very short term usageDiscrete Logarithm NotationDescribing Discrete Logarithm Assumption

When is phishing education going too far?

ListPlot join points by nearest neighbor rather than order

Are my PIs rude or am I just being too sensitive?

IndentationError when pasting code in Python 3 interpreter mode

What would be the ideal power source for a cybernetic eye?

Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?

Should I call the interviewer directly, if HR aren't responding?

Why is "Consequences inflicted." not a sentence?

What does the "x" in "x86" represent?

How was the dust limit of 546 satoshis was chosen? Why not 550 satoshis?

How to say 'striped' in Latin

Did Xerox really develop the first LAN?

Java 8 stream max() function argument type Comparator vs Comparable

What happens to sewage if there is no river near by?

List *all* the tuples!

Is it true that "carbohydrates are of no use for the basal metabolic need"?

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

How do I keep my slimes from escaping their pens?

The logistics of corpse disposal

What are the pros and cons of Aerospike nosecones?

How does a biquinary adder work?

How to motivate offshore teams and trust them to deliver?

Why is black pepper both grey and black?

Why is "Captain Marvel" translated as male in Portugal?



Why was the term “discrete” used in discrete logarithm?



Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Trying to better understand the failure of the Index Calculus for ECDLPWhat is so special about elliptic curves?Why is the discrete logarithm problem assumed to be hard?What is the difference between discrete logarithm and logarithm?Calculating the discrete logarithmWhy is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?How to construct a hash function into a cyclic group such that its discrete log is intractable?Discrete logarithm key sizes for very short term usageDiscrete Logarithm NotationDescribing Discrete Logarithm Assumption










2












$begingroup$


Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?



The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?










share|improve this question









$endgroup$







  • 1




    $begingroup$
    Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
    $endgroup$
    – Mikero
    1 hour ago















2












$begingroup$


Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?



The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?










share|improve this question









$endgroup$







  • 1




    $begingroup$
    Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
    $endgroup$
    – Mikero
    1 hour ago













2












2








2





$begingroup$


Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?



The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?










share|improve this question









$endgroup$




Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?



The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?







discrete-logarithm terminology






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 1 hour ago









JohnGaltJohnGalt

22816




22816







  • 1




    $begingroup$
    Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
    $endgroup$
    – Mikero
    1 hour ago












  • 1




    $begingroup$
    Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
    $endgroup$
    – Mikero
    1 hour ago







1




1




$begingroup$
Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
$endgroup$
– Mikero
1 hour ago




$begingroup$
Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $mathbbZ_n$.
$endgroup$
– Mikero
1 hour ago










2 Answers
2






active

oldest

votes


















5












$begingroup$

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.



The standard logarithmic problem is over the infinite group $mathbbR^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.



The discrete logarithmic problem is over a finite group (for example, $mathbbZ_p^*$); in contrast to $mathbbR^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.






share|improve this answer









$endgroup$








  • 1




    $begingroup$
    yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
    $endgroup$
    – Geoffroy Couteau
    46 mins ago






  • 1




    $begingroup$
    @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
    $endgroup$
    – Mark
    46 mins ago






  • 1




    $begingroup$
    my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
    $endgroup$
    – Geoffroy Couteau
    37 mins ago






  • 1




    $begingroup$
    @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
    $endgroup$
    – Mark
    33 mins ago






  • 1




    $begingroup$
    @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
    $endgroup$
    – Geoffroy Couteau
    30 mins ago


















3












$begingroup$

While I agree completely with poncho's answer, this other viewpoint might be useful.
Specifically, I think a better comparison isn't between $mathbbZ_p^*$ and $mathbbR^*$, but with $mathbbZ_p^*$ and $S^1$. We can view $S^1 cong = 1$. It's not hard to show that any $zin S^1$ is able to be written as $z = exp(2pi i t)$ for $tinmathbbR$ (we don't strictly need the factor $2pi$ here, but it's traditional). Due to $exp(x)$ being periodic, it's in fact enough to have $tin[0,1)$.



This has an obvious group structure, in that:
$$exp(2pi i t_0)exp(2pi i t_1) = exp(2pi i (t_0+t_1))$$
If we're making the restriction that $t_iin[0,1)$, then we have to take $t_0+t_1mod 1$, but this is fairly standard.



More than just having an obvious group structure, we actually have that any $mathbbZ_p^*$ injects into it.
Specifically, we always have:
$$
phi_p:mathbbZ_p^*to S^1,quad phi_p(x) = exp(2pi i x/(p-1))
$$

Here, $p-1$ in the denominator is because $|mathbbZ_p^*| = p-1$.
We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_iin[0, 1)$ if we want a unique answer).
Then, we can relate these problems to each via the aforementioned injection.
Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $mathbbZ_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).






share|improve this answer









$endgroup$













    Your Answer








    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
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68801%2fwhy-was-the-term-discrete-used-in-discrete-logarithm%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    5












    $begingroup$

    The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.



    The standard logarithmic problem is over the infinite group $mathbbR^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.



    The discrete logarithmic problem is over a finite group (for example, $mathbbZ_p^*$); in contrast to $mathbbR^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.






    share|improve this answer









    $endgroup$








    • 1




      $begingroup$
      yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
      $endgroup$
      – Geoffroy Couteau
      46 mins ago






    • 1




      $begingroup$
      @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
      $endgroup$
      – Mark
      46 mins ago






    • 1




      $begingroup$
      my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
      $endgroup$
      – Geoffroy Couteau
      37 mins ago






    • 1




      $begingroup$
      @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
      $endgroup$
      – Mark
      33 mins ago






    • 1




      $begingroup$
      @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
      $endgroup$
      – Geoffroy Couteau
      30 mins ago















    5












    $begingroup$

    The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.



    The standard logarithmic problem is over the infinite group $mathbbR^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.



    The discrete logarithmic problem is over a finite group (for example, $mathbbZ_p^*$); in contrast to $mathbbR^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.






    share|improve this answer









    $endgroup$








    • 1




      $begingroup$
      yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
      $endgroup$
      – Geoffroy Couteau
      46 mins ago






    • 1




      $begingroup$
      @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
      $endgroup$
      – Mark
      46 mins ago






    • 1




      $begingroup$
      my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
      $endgroup$
      – Geoffroy Couteau
      37 mins ago






    • 1




      $begingroup$
      @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
      $endgroup$
      – Mark
      33 mins ago






    • 1




      $begingroup$
      @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
      $endgroup$
      – Geoffroy Couteau
      30 mins ago













    5












    5








    5





    $begingroup$

    The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.



    The standard logarithmic problem is over the infinite group $mathbbR^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.



    The discrete logarithmic problem is over a finite group (for example, $mathbbZ_p^*$); in contrast to $mathbbR^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.






    share|improve this answer









    $endgroup$



    The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.



    The standard logarithmic problem is over the infinite group $mathbbR^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.



    The discrete logarithmic problem is over a finite group (for example, $mathbbZ_p^*$); in contrast to $mathbbR^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered 1 hour ago









    ponchoponcho

    94.2k2148247




    94.2k2148247







    • 1




      $begingroup$
      yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
      $endgroup$
      – Geoffroy Couteau
      46 mins ago






    • 1




      $begingroup$
      @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
      $endgroup$
      – Mark
      46 mins ago






    • 1




      $begingroup$
      my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
      $endgroup$
      – Geoffroy Couteau
      37 mins ago






    • 1




      $begingroup$
      @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
      $endgroup$
      – Mark
      33 mins ago






    • 1




      $begingroup$
      @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
      $endgroup$
      – Geoffroy Couteau
      30 mins ago












    • 1




      $begingroup$
      yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
      $endgroup$
      – Geoffroy Couteau
      46 mins ago






    • 1




      $begingroup$
      @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
      $endgroup$
      – Mark
      46 mins ago






    • 1




      $begingroup$
      my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
      $endgroup$
      – Geoffroy Couteau
      37 mins ago






    • 1




      $begingroup$
      @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
      $endgroup$
      – Mark
      33 mins ago






    • 1




      $begingroup$
      @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
      $endgroup$
      – Geoffroy Couteau
      30 mins ago







    1




    1




    $begingroup$
    yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
    $endgroup$
    – Geoffroy Couteau
    46 mins ago




    $begingroup$
    yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way.
    $endgroup$
    – Geoffroy Couteau
    46 mins ago




    1




    1




    $begingroup$
    @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
    $endgroup$
    – Mark
    46 mins ago




    $begingroup$
    @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently.
    $endgroup$
    – Mark
    46 mins ago




    1




    1




    $begingroup$
    my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
    $endgroup$
    – Geoffroy Couteau
    37 mins ago




    $begingroup$
    my point is just the following: when you manipulate concrete number on your computer, they will have to come from some discrete structure, since you cannot represent numbers with arbitrary precision (hence you cannot accurately represent elements of a continuous set such as the reals). Hence, you will need your problem to be hard over a discrete structure anyway, even though being discrete is not what makes it hard.
    $endgroup$
    – Geoffroy Couteau
    37 mins ago




    1




    1




    $begingroup$
    @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
    $endgroup$
    – Mark
    33 mins ago




    $begingroup$
    @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $mathbbQ$ as a sub-field).
    $endgroup$
    – Mark
    33 mins ago




    1




    1




    $begingroup$
    @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
    $endgroup$
    – Geoffroy Couteau
    30 mins ago




    $begingroup$
    @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography.
    $endgroup$
    – Geoffroy Couteau
    30 mins ago











    3












    $begingroup$

    While I agree completely with poncho's answer, this other viewpoint might be useful.
    Specifically, I think a better comparison isn't between $mathbbZ_p^*$ and $mathbbR^*$, but with $mathbbZ_p^*$ and $S^1$. We can view $S^1 cong = 1$. It's not hard to show that any $zin S^1$ is able to be written as $z = exp(2pi i t)$ for $tinmathbbR$ (we don't strictly need the factor $2pi$ here, but it's traditional). Due to $exp(x)$ being periodic, it's in fact enough to have $tin[0,1)$.



    This has an obvious group structure, in that:
    $$exp(2pi i t_0)exp(2pi i t_1) = exp(2pi i (t_0+t_1))$$
    If we're making the restriction that $t_iin[0,1)$, then we have to take $t_0+t_1mod 1$, but this is fairly standard.



    More than just having an obvious group structure, we actually have that any $mathbbZ_p^*$ injects into it.
    Specifically, we always have:
    $$
    phi_p:mathbbZ_p^*to S^1,quad phi_p(x) = exp(2pi i x/(p-1))
    $$

    Here, $p-1$ in the denominator is because $|mathbbZ_p^*| = p-1$.
    We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_iin[0, 1)$ if we want a unique answer).
    Then, we can relate these problems to each via the aforementioned injection.
    Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $mathbbZ_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).






    share|improve this answer









    $endgroup$

















      3












      $begingroup$

      While I agree completely with poncho's answer, this other viewpoint might be useful.
      Specifically, I think a better comparison isn't between $mathbbZ_p^*$ and $mathbbR^*$, but with $mathbbZ_p^*$ and $S^1$. We can view $S^1 cong = 1$. It's not hard to show that any $zin S^1$ is able to be written as $z = exp(2pi i t)$ for $tinmathbbR$ (we don't strictly need the factor $2pi$ here, but it's traditional). Due to $exp(x)$ being periodic, it's in fact enough to have $tin[0,1)$.



      This has an obvious group structure, in that:
      $$exp(2pi i t_0)exp(2pi i t_1) = exp(2pi i (t_0+t_1))$$
      If we're making the restriction that $t_iin[0,1)$, then we have to take $t_0+t_1mod 1$, but this is fairly standard.



      More than just having an obvious group structure, we actually have that any $mathbbZ_p^*$ injects into it.
      Specifically, we always have:
      $$
      phi_p:mathbbZ_p^*to S^1,quad phi_p(x) = exp(2pi i x/(p-1))
      $$

      Here, $p-1$ in the denominator is because $|mathbbZ_p^*| = p-1$.
      We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_iin[0, 1)$ if we want a unique answer).
      Then, we can relate these problems to each via the aforementioned injection.
      Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $mathbbZ_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).






      share|improve this answer









      $endgroup$















        3












        3








        3





        $begingroup$

        While I agree completely with poncho's answer, this other viewpoint might be useful.
        Specifically, I think a better comparison isn't between $mathbbZ_p^*$ and $mathbbR^*$, but with $mathbbZ_p^*$ and $S^1$. We can view $S^1 cong = 1$. It's not hard to show that any $zin S^1$ is able to be written as $z = exp(2pi i t)$ for $tinmathbbR$ (we don't strictly need the factor $2pi$ here, but it's traditional). Due to $exp(x)$ being periodic, it's in fact enough to have $tin[0,1)$.



        This has an obvious group structure, in that:
        $$exp(2pi i t_0)exp(2pi i t_1) = exp(2pi i (t_0+t_1))$$
        If we're making the restriction that $t_iin[0,1)$, then we have to take $t_0+t_1mod 1$, but this is fairly standard.



        More than just having an obvious group structure, we actually have that any $mathbbZ_p^*$ injects into it.
        Specifically, we always have:
        $$
        phi_p:mathbbZ_p^*to S^1,quad phi_p(x) = exp(2pi i x/(p-1))
        $$

        Here, $p-1$ in the denominator is because $|mathbbZ_p^*| = p-1$.
        We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_iin[0, 1)$ if we want a unique answer).
        Then, we can relate these problems to each via the aforementioned injection.
        Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $mathbbZ_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).






        share|improve this answer









        $endgroup$



        While I agree completely with poncho's answer, this other viewpoint might be useful.
        Specifically, I think a better comparison isn't between $mathbbZ_p^*$ and $mathbbR^*$, but with $mathbbZ_p^*$ and $S^1$. We can view $S^1 cong = 1$. It's not hard to show that any $zin S^1$ is able to be written as $z = exp(2pi i t)$ for $tinmathbbR$ (we don't strictly need the factor $2pi$ here, but it's traditional). Due to $exp(x)$ being periodic, it's in fact enough to have $tin[0,1)$.



        This has an obvious group structure, in that:
        $$exp(2pi i t_0)exp(2pi i t_1) = exp(2pi i (t_0+t_1))$$
        If we're making the restriction that $t_iin[0,1)$, then we have to take $t_0+t_1mod 1$, but this is fairly standard.



        More than just having an obvious group structure, we actually have that any $mathbbZ_p^*$ injects into it.
        Specifically, we always have:
        $$
        phi_p:mathbbZ_p^*to S^1,quad phi_p(x) = exp(2pi i x/(p-1))
        $$

        Here, $p-1$ in the denominator is because $|mathbbZ_p^*| = p-1$.
        We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_iin[0, 1)$ if we want a unique answer).
        Then, we can relate these problems to each via the aforementioned injection.
        Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $mathbbZ_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered 49 mins ago









        MarkMark

        1835




        1835



























            draft saved

            draft discarded
















































            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%2f68801%2fwhy-was-the-term-discrete-used-in-discrete-logarithm%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

            Category:Fedor von Bock Media in category "Fedor von Bock"Navigation menuUpload mediaISNI: 0000 0000 5511 3417VIAF ID: 24712551GND ID: 119294796Library of Congress authority ID: n96068363BnF ID: 12534305fSUDOC authorities ID: 034604189Open Library ID: OL338253ANKCR AUT ID: jn19990000869National Library of Israel ID: 000514068National Thesaurus for Author Names ID: 341574317ReasonatorScholiaStatistics

            Reverse int within the 32-bit signed integer range: [−2^31, 2^31 − 1]Combining two 32-bit integers into one 64-bit integerDetermine if an int is within rangeLossy packing 32 bit integer to 16 bitComputing the square root of a 64-bit integerKeeping integer addition within boundsSafe multiplication of two 64-bit signed integersLeetcode 10: Regular Expression MatchingSigned integer-to-ascii x86_64 assembler macroReverse the digits of an Integer“Add two numbers given in reverse order from a linked list”

            Log på Navigationsmenu