Does classifying an integer as a discrete log require it be part of a multiplicative group? ...
Fundamental Solution of the Pell Equation
Is grep documentation wrong?
Is safe to use va_start macro with this as parameter?
old style "caution" boxes
Is there any way for the UK Prime Minister to make a motion directly dependent on Government confidence?
Do wooden building fires get hotter than 600°C?
Did MS DOS itself ever use blinking text?
Extracting terms with certain heads in a function
Do jazz musicians improvise on the parent scale in addition to the chord-scales?
What do you call a floor made of glass so you can see through the floor?
How do pianists reach extremely loud dynamics?
Can an alien society believe that their star system is the universe?
How come Sam didn't become Lord of Horn Hill?
How to Make a Beautiful Stacked 3D Plot
Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?
How can I use the Python library networkx from Mathematica?
Circuit to "zoom in" on mV fluctuations of a DC signal?
For a new assistant professor in CS, how to build/manage a publication pipeline
Is there such thing as an Availability Group failover trigger?
Trademark violation for app?
Delete nth line from bottom
If my PI received research grants from a company to be able to pay my postdoc salary, did I have a potential conflict interest too?
Dating a Former Employee
How to react to hostile behavior from a senior developer?
Does classifying an integer as a discrete log require it be part of a multiplicative group?
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?Why was the term “discrete” used in discrete logarithm?Discrete log problem, when we have many examplesFinding where I am in a linear recurrence relationA discrete-log-like problem, with matrices: given $A^k x$, find $k$iterated discrete log problemWhy can ECC key sizes be smaller than RSA keys for similar security?Is the reverse of the “discrete logarithm problem” equally dificult?How to construct a hash function into a cyclic group such that its discrete log is intractable?The computational complexity of discrete logSolving the discrete logarithm problem for a weak groupSolving discrete log in partially known group
$begingroup$
This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.
The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.
For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.
discrete-logarithm terminology
asked 9 hours ago
JohnGaltJohnGalt
28528
$endgroup$
|
show 10 more comments
$begingroup$
This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.
The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.
For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.
discrete-logarithm terminology
asked 9 hours ago
JohnGaltJohnGalt
28528
$endgroup$
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
1
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
1
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago
|
show 10 more comments
$begingroup$
This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.
The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.
For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.
discrete-logarithm terminology
asked 9 hours ago
JohnGaltJohnGalt
28528
$endgroup$
This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.
The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.
For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.
discrete-logarithm terminology
discrete-logarithm terminology
asked 9 hours ago
JohnGaltJohnGalt
28528
asked 9 hours ago
JohnGaltJohnGalt
28528
asked 9 hours ago
JohnGaltJohnGalt
28528
asked 9 hours ago
JohnGaltJohnGalt
28528
asked 9 hours ago
JohnGaltJohnGalt
28528
28528
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
1
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
1
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago
|
show 10 more comments
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
1
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
1
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
1
1
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
1
1
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago
|
show 10 more comments
2 Answers
2
active
oldest
votes
$begingroup$
The discrete logarithm $log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.
If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.
Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $gcd(k,n) neq 1$. Now the $g'$ will generate a subgroup $G'leqslant G$, not the full group. Then any element of the full group $ a in G$ and $a notin G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.
When we consider the non-zero elements of a field $Fbackslash{0}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 8 hours ago
kelalakakelalaka
8,87532351
$endgroup$
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
add a comment |
$begingroup$
Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.
Another convenient way to consider the set of discrete logarithms is as the ring $mathbf Z/nmathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.
Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.
answered 7 hours ago
fkraiemfkraiem
6,81021733
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
|
show 1 more 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%2f68851%2fdoes-classifying-an-integer-as-a-discrete-log-require-it-be-part-of-a-multiplica%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 discrete logarithm $log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.
If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.
Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $gcd(k,n) neq 1$. Now the $g'$ will generate a subgroup $G'leqslant G$, not the full group. Then any element of the full group $ a in G$ and $a notin G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.
When we consider the non-zero elements of a field $Fbackslash{0}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 8 hours ago
kelalakakelalaka
8,87532351
$endgroup$
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
add a comment |
$begingroup$
The discrete logarithm $log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.
If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.
Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $gcd(k,n) neq 1$. Now the $g'$ will generate a subgroup $G'leqslant G$, not the full group. Then any element of the full group $ a in G$ and $a notin G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.
When we consider the non-zero elements of a field $Fbackslash{0}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 8 hours ago
kelalakakelalaka
8,87532351
$endgroup$
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
add a comment |
$begingroup$
The discrete logarithm $log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.
If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.
Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $gcd(k,n) neq 1$. Now the $g'$ will generate a subgroup $G'leqslant G$, not the full group. Then any element of the full group $ a in G$ and $a notin G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.
When we consider the non-zero elements of a field $Fbackslash{0}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 8 hours ago
kelalakakelalaka
8,87532351
$endgroup$
The discrete logarithm $log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.
If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.
Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $gcd(k,n) neq 1$. Now the $g'$ will generate a subgroup $G'leqslant G$, not the full group. Then any element of the full group $ a in G$ and $a notin G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.
When we consider the non-zero elements of a field $Fbackslash{0}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 8 hours ago
kelalakakelalaka
8,87532351
edited 7 hours ago
answered 8 hours ago
kelalakakelalaka
8,87532351
answered 8 hours ago
kelalakakelalaka
8,87532351
answered 8 hours ago
kelalakakelalaka
8,87532351
8,87532351
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
add a comment |
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd.
$endgroup$
– fkraiem
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
7 hours ago
add a comment |
$begingroup$
Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.
Another convenient way to consider the set of discrete logarithms is as the ring $mathbf Z/nmathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.
Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.
answered 7 hours ago
fkraiemfkraiem
6,81021733
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
|
show 1 more comment
$begingroup$
Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.
Another convenient way to consider the set of discrete logarithms is as the ring $mathbf Z/nmathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.
Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.
answered 7 hours ago
fkraiemfkraiem
6,81021733
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
|
show 1 more comment
$begingroup$
Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.
Another convenient way to consider the set of discrete logarithms is as the ring $mathbf Z/nmathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.
Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.
answered 7 hours ago
fkraiemfkraiem
6,81021733
$endgroup$
Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.
Another convenient way to consider the set of discrete logarithms is as the ring $mathbf Z/nmathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.
Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.
answered 7 hours ago
fkraiemfkraiem
6,81021733
answered 7 hours ago
fkraiemfkraiem
6,81021733
answered 7 hours ago
fkraiemfkraiem
6,81021733
answered 7 hours ago
fkraiemfkraiem
6,81021733
6,81021733
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
|
show 1 more comment
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
I was just looking for an example of a group element which would not generate anything but itself. I guess copies of Z/2Z is what I should have gone with. But it's not an interesting example. What about Z/nZ, where n = p^l? What is the discrete log of 1+p^l-p^(l-1)? p is a prime, of course.
$endgroup$
– grovkin
6 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
@grovkin To talk about discrete logs, you need a cyclic group and a generator. If your group is Z/nZ (additive) with generator 1, the discrete log of k is k.
$endgroup$
– fkraiem
5 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
$begingroup$
discrete log refers to solution of log_b(a) in a ring Z/nZ. Let's make it really concrete. in Z/9Z, what number is 7 a discrete log of? I didn't pick p^l-p^(l-1) out of nowhere. It's the number of units in the Z/(p^l)Z ring. So no number in this ring will have (multiplicative) order larger than p^l-p^(l-1). So 1+p^l-p^(l-1) cannot be a power to which any number needs to be raised to get another number. Hence the example: no number in Z/9Z can have a discrete log of 7.
$endgroup$
– grovkin
3 hours ago
|
show 1 more 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%2f68851%2fdoes-classifying-an-integer-as-a-discrete-log-require-it-be-part-of-a-multiplica%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
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
@kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log?
$endgroup$
– JohnGalt
8 hours ago
$begingroup$
Whomever down voted my question, I respect the decision, however, it would be helpful if you commented as to why you down voted it.
$endgroup$
– JohnGalt
7 hours ago
1
$begingroup$
@JohnGalt In the statement you quoted, the context is discrete logs in $mathbb Z/nmathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h in mathbb Z/nmathbb Z$ such that $x = log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $mathbb Z/nmathbb Z$.
$endgroup$
– Squeamish Ossifrage
1 hour ago
1
$begingroup$
By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(mathbf Z/nmathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed.
$endgroup$
– fkraiem
25 mins ago