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

Do I really need to have a message in a novel to appeal to readers?

On SQL Server, is it possible to restrict certain users from using certain functions, operators or statements?

An adverb for when you're not exaggerating

Why didn't Eitri join the fight?

What is homebrew?

Why wasn't DOSKEY integrated with COMMAND.COM?

Do I really need recursive chmod to restrict access to a folder?

Would "destroying" Wurmcoil Engine prevent its tokens from being created?

What are the best places to gain the most altitude in a glider?

Trademark violation for app?

Is it fair for a professor to grade us on the possession of past papers?

Is there any way for the UK Prime Minister to make a motion directly dependent on Government confidence?

Does classifying an integer as a discrete log require it be part of a multiplicative group?

How do I find out the mythology and history of my Fortress?

What causes the direction of lightning flashes?

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

What does "lightly crushed" mean for cardamon pods?

Can you shove before Attacking with Shield Master using a Readied action?

Fundamental Solution of the Pell Equation

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

Closed form of recurrent arithmetic series summation

Why do we bend a book to keep it straight?

What is this building called? (It was built in 2002)

How to answer "Have you ever been terminated?"



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










2












$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.










share|improve this question









$endgroup$











  • $begingroup$
    @kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
    $endgroup$
    – JohnGalt
    4 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
    4 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
    3 hours ago










  • $begingroup$
    Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
    $endgroup$
    – Ilmari Karonen
    45 mins ago











  • $begingroup$
    (In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
    $endgroup$
    – Ilmari Karonen
    37 mins ago
















2












$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.










share|improve this question









$endgroup$











  • $begingroup$
    @kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
    $endgroup$
    – JohnGalt
    4 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
    4 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
    3 hours ago










  • $begingroup$
    Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
    $endgroup$
    – Ilmari Karonen
    45 mins ago











  • $begingroup$
    (In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
    $endgroup$
    – Ilmari Karonen
    37 mins ago














2












2








2





$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.










share|improve this question









$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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 4 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
    4 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
    4 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
    3 hours ago










  • $begingroup$
    Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
    $endgroup$
    – Ilmari Karonen
    45 mins ago











  • $begingroup$
    (In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
    $endgroup$
    – Ilmari Karonen
    37 mins ago

















  • $begingroup$
    @kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
    $endgroup$
    – JohnGalt
    4 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
    4 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
    3 hours ago










  • $begingroup$
    Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
    $endgroup$
    – Ilmari Karonen
    45 mins ago











  • $begingroup$
    (In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
    $endgroup$
    – Ilmari Karonen
    37 mins ago
















$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
4 hours ago




$begingroup$
@kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm."
$endgroup$
– JohnGalt
4 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
4 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
4 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
3 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
3 hours ago












$begingroup$
Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
$endgroup$
– Ilmari Karonen
45 mins ago





$begingroup$
Your question currently has no downvotes. That said, I'm tempted to vote to close it as unclear, since it seems to be based on some kind of a confusion of terminology, and it's literally not clear to me what you're trying to ask. The two answers already below are both correct and well written, but they answer completely different questions.
$endgroup$
– Ilmari Karonen
45 mins ago













$begingroup$
(In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
$endgroup$
– Ilmari Karonen
37 mins ago





$begingroup$
(In particular, every integer is, trivially, both a part of infinitely many different multiplicative groups and the discrete logarithm of infinitely many elements of some multiplicative group with respect to some base. And these two facts have nothing to do with each other.)
$endgroup$
– Ilmari Karonen
37 mins ago











2 Answers
2






active

oldest

votes


















4












$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.






share|improve this answer











$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
    2 hours ago










  • $begingroup$
    @fkraiem updated to guarantee that $g^k$ is generates a subgroup.
    $endgroup$
    – kelalaka
    2 hours ago


















3












$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.






share|improve this answer









$endgroup$












  • $begingroup$
    what if n is a square? If n = k^2, then k is not a discrete log mod n.
    $endgroup$
    – grovkin
    2 hours ago










  • $begingroup$
    @grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
    $endgroup$
    – fkraiem
    2 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
    1 hour 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
    1 hour ago












Your Answer








StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













draft saved

draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%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









4












$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.






share|improve this answer











$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
    2 hours ago










  • $begingroup$
    @fkraiem updated to guarantee that $g^k$ is generates a subgroup.
    $endgroup$
    – kelalaka
    2 hours ago















4












$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.






share|improve this answer











$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
    2 hours ago










  • $begingroup$
    @fkraiem updated to guarantee that $g^k$ is generates a subgroup.
    $endgroup$
    – kelalaka
    2 hours ago













4












4








4





$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.






share|improve this answer











$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.







share|improve this answer














share|improve this answer



share|improve this answer








edited 2 hours ago

























answered 3 hours ago









kelalakakelalaka

8,86532351




8,86532351











  • $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
    2 hours ago










  • $begingroup$
    @fkraiem updated to guarantee that $g^k$ is generates a subgroup.
    $endgroup$
    – kelalaka
    2 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
    2 hours ago










  • $begingroup$
    @fkraiem updated to guarantee that $g^k$ is generates a subgroup.
    $endgroup$
    – kelalaka
    2 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
2 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
2 hours ago












$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
2 hours ago




$begingroup$
@fkraiem updated to guarantee that $g^k$ is generates a subgroup.
$endgroup$
– kelalaka
2 hours ago











3












$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.






share|improve this answer









$endgroup$












  • $begingroup$
    what if n is a square? If n = k^2, then k is not a discrete log mod n.
    $endgroup$
    – grovkin
    2 hours ago










  • $begingroup$
    @grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
    $endgroup$
    – fkraiem
    2 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
    1 hour 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
    1 hour ago
















3












$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.






share|improve this answer









$endgroup$












  • $begingroup$
    what if n is a square? If n = k^2, then k is not a discrete log mod n.
    $endgroup$
    – grovkin
    2 hours ago










  • $begingroup$
    @grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
    $endgroup$
    – fkraiem
    2 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
    1 hour 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
    1 hour ago














3












3








3





$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.






share|improve this answer









$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.







share|improve this answer












share|improve this answer



share|improve this answer










answered 3 hours ago









fkraiemfkraiem

6,80021732




6,80021732











  • $begingroup$
    what if n is a square? If n = k^2, then k is not a discrete log mod n.
    $endgroup$
    – grovkin
    2 hours ago










  • $begingroup$
    @grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
    $endgroup$
    – fkraiem
    2 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
    1 hour 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
    1 hour ago

















  • $begingroup$
    what if n is a square? If n = k^2, then k is not a discrete log mod n.
    $endgroup$
    – grovkin
    2 hours ago










  • $begingroup$
    @grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
    $endgroup$
    – fkraiem
    2 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
    1 hour 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
    1 hour ago
















$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
2 hours ago




$begingroup$
what if n is a square? If n = k^2, then k is not a discrete log mod n.
$endgroup$
– grovkin
2 hours ago












$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
2 hours ago





$begingroup$
@grovkin Why not? $k$ is a discrete log of $g^k$. Are you confusing it with quadratic residue?
$endgroup$
– fkraiem
2 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
1 hour 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
1 hour 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
1 hour 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
1 hour ago


















draft saved

draft discarded
















































Thanks for contributing an answer to Cryptography Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid


  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%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





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Oświęcim Innehåll Historia | Källor | Externa länkar | Navigeringsmeny50°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.2213950°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.221393089658Nordisk familjebok, AuschwitzInsidan tro och existensJewish Community i OświęcimAuschwitz Jewish Center: MuseumAuschwitz Jewish Center

Valle di Casies Indice Geografia fisica | Origini del nome | Storia | Società | Amministrazione | Sport | Note | Bibliografia | Voci correlate | Altri progetti | Collegamenti esterni | Menu di navigazione46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)Sito istituzionaleAstat Censimento della popolazione 2011 - Determinazione della consistenza dei tre gruppi linguistici della Provincia Autonoma di Bolzano-Alto Adige - giugno 2012Numeri e fattiValle di CasiesDato IstatTabella dei gradi/giorno dei Comuni italiani raggruppati per Regione e Provincia26 agosto 1993, n. 412Heraldry of the World: GsiesStatistiche I.StatValCasies.comWikimedia CommonsWikimedia CommonsValle di CasiesSito ufficialeValle di CasiesMM14870458910042978-6

Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager