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?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
What would be the ideal power source for a cybernetic eye?
Is it fair for a professor to grade us on the possession of past papers?
What is the escape velocity of a neutron particle (not neutron star)
Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?
What does "lightly crushed" mean for cardamon pods?
What are the out-of-universe reasons for the references to Toby Maguire-era Spider-Man in ITSV
Novel: non-telepath helps overthrow rule by telepaths
8 Prisoners wearing hats
Wu formula for manifolds with boundary
Do I really need recursive chmod to restrict access to a folder?
Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?
Is the Standard Deduction better than Itemized when both are the same amount?
Delete nth line from bottom
Significance of Cersei's obsession with elephants?
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?
また usage in a dictionary
Should I use a zero-interest credit card for a large one-time purchase?
How to show element name in portuguese using elements package?
Compare a given version number in the form major.minor.build.patch and see if one is less than the other
Do wooden building fires get hotter than 600°C?
Apollo command module space walk?
Is it common practice to audition new musicians 1-2-1 before rehearsing with the entire band?
2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?
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?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 2 hours ago
JohnGaltJohnGalt
28528
$endgroup$
add a comment |
$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 2 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
2 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
2 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
1 hour ago
add a comment |
$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 2 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 2 hours ago
JohnGaltJohnGalt
28528
asked 2 hours ago
JohnGaltJohnGalt
28528
asked 2 hours ago
JohnGaltJohnGalt
28528
asked 2 hours ago
JohnGaltJohnGalt
28528
asked 2 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
2 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
2 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
1 hour ago
add a comment |
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
2 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
2 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
1 hour ago
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
2 hours ago
$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
2 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
2 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
2 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
1 hour 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
1 hour ago
add a comment |
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 $Fbackslash0$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 1 hour ago
kelalakakelalaka
8,84532351
$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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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 1 hour ago
fkraiemfkraiem
6,79021732
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs ago
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%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 $Fbackslash0$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 1 hour ago
kelalakakelalaka
8,84532351
$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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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 $Fbackslash0$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 1 hour ago
kelalakakelalaka
8,84532351
$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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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 $Fbackslash0$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 1 hour ago
kelalakakelalaka
8,84532351
$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 $Fbackslash0$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.
answered 1 hour ago
kelalakakelalaka
8,84532351
edited 40 mins ago
answered 1 hour ago
kelalakakelalaka
8,84532351
answered 1 hour ago
kelalakakelalaka
8,84532351
answered 1 hour ago
kelalakakelalaka
8,84532351
8,84532351
$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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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
52 mins 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
52 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins ago
$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
38 mins 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 1 hour ago
fkraiemfkraiem
6,79021732
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs 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 1 hour ago
fkraiemfkraiem
6,79021732
$endgroup$
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs 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 1 hour ago
fkraiemfkraiem
6,79021732
$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 1 hour ago
fkraiemfkraiem
6,79021732
answered 1 hour ago
fkraiemfkraiem
6,79021732
answered 1 hour ago
fkraiemfkraiem
6,79021732
answered 1 hour ago
fkraiemfkraiem
6,79021732
6,79021732
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs ago
add a comment |
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs ago
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
7 mins ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs ago
$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$.
$endgroup$
– fkraiem
34 secs ago
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%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
2 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
2 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
1 hour ago