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
$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?
discrete-logarithm terminology
$endgroup$
add a comment |
$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?
discrete-logarithm terminology
$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
add a comment |
$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?
discrete-logarithm terminology
$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
discrete-logarithm terminology
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
add a comment |
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
add a comment |
2 Answers
2
active
oldest
votes
$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'.
$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
|
show 4 more comments
$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).
$endgroup$
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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'.
$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
|
show 4 more comments
$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'.
$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
|
show 4 more comments
$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'.
$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'.
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
|
show 4 more comments
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
|
show 4 more comments
$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).
$endgroup$
add a comment |
$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).
$endgroup$
add a comment |
$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).
$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).
answered 49 mins ago
MarkMark
1835
1835
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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