Mixing
In Mathematics is there a discrete logarithm function?
$begingroup$
I find it difficult to understand this part in this book.
Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is this formula to direct calculate the discrete logarithm?
Or is there a direct unique formula or funtion that calculates special discrete logarithms?
discrete-mathematics special-functions math-history cryptography discrete-logarithms
asked Jan 23 at 5:14
NewuserNewuser
314213
$endgroup$
add a comment |
$begingroup$
I find it difficult to understand this part in this book.
Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is this formula to direct calculate the discrete logarithm?
Or is there a direct unique formula or funtion that calculates special discrete logarithms?
discrete-mathematics special-functions math-history cryptography discrete-logarithms
asked Jan 23 at 5:14
NewuserNewuser
314213
$endgroup$
$begingroup$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
2
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03
add a comment |
$begingroup$
I find it difficult to understand this part in this book.
Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is this formula to direct calculate the discrete logarithm?
Or is there a direct unique formula or funtion that calculates special discrete logarithms?
discrete-mathematics special-functions math-history cryptography discrete-logarithms
asked Jan 23 at 5:14
NewuserNewuser
314213
$endgroup$
I find it difficult to understand this part in this book.
Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is this formula to direct calculate the discrete logarithm?
Or is there a direct unique formula or funtion that calculates special discrete logarithms?
discrete-mathematics special-functions math-history cryptography discrete-logarithms
discrete-mathematics special-functions math-history cryptography discrete-logarithms
asked Jan 23 at 5:14
NewuserNewuser
314213
asked Jan 23 at 5:14
NewuserNewuser
314213
edited Jan 23 at 5:37
Newuser
asked Jan 23 at 5:14
NewuserNewuser
314213
asked Jan 23 at 5:14
NewuserNewuser
314213
asked Jan 23 at 5:14
NewuserNewuser
314213
314213
$begingroup$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
2
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03
add a comment |
$begingroup$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
2
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03
$begingroup$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
2
2
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $unotequiv 0mod p$ then $log_g u$ is $min{L: g^L equiv umod n, Lge 0}$. This is always an integer in $[0,p-2]$.
Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fmath.stackexchange.com%2fquestions%2f3084107%2fin-mathematics-is-there-a-discrete-logarithm-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $unotequiv 0mod p$ then $log_g u$ is $min{L: g^L equiv umod n, Lge 0}$. This is always an integer in $[0,p-2]$.
Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
$endgroup$
add a comment |
$begingroup$
The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $unotequiv 0mod p$ then $log_g u$ is $min{L: g^L equiv umod n, Lge 0}$. This is always an integer in $[0,p-2]$.
Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
$endgroup$
add a comment |
$begingroup$
The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $unotequiv 0mod p$ then $log_g u$ is $min{L: g^L equiv umod n, Lge 0}$. This is always an integer in $[0,p-2]$.
Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
$endgroup$
The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $unotequiv 0mod p$ then $log_g u$ is $min{L: g^L equiv umod n, Lge 0}$. This is always an integer in $[0,p-2]$.
Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
answered Jan 23 at 5:53
jmerryjmerry
13.6k1629
13.6k1629
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3084107%2fin-mathematics-is-there-a-discrete-logarithm-function%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$
You need to unknow what you know, because it is wrong. There very mush is a function, and behold, even a formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:47
$begingroup$
@IvanNeretin unique formula?
$endgroup$
– Newuser
Jan 23 at 5:52
$begingroup$
There is no such thing as unique formula.
$endgroup$
– Ivan Neretin
Jan 23 at 5:53
2
$begingroup$
Once you have fixed a generator $g$, every non-zero element is of the form $g^k$ for some integer $k$. If you restrict $1leq k leq p-1$, there there is exactly only one $k$. So the function must be unique: if $h = g^r$ then the discrete log function $f$ must give you exactly $f(h) = r$. However since we can define multiple formulas for $f$, there is no unique formula. In particular the one you listed, by Wells, is one such formula (I guess your question would extend to proving this formula).
$endgroup$
– Yong Hao Ng
Jan 23 at 6:03