Mixing
Lower bounds for totient function of a Carmichael number
$begingroup$
Short version: I am wondering if there are any good bounds of the form $phi(n) geq f(n)cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number.
Long version: Consider Fermat's test in the following form for an odd integer $n>2$:
choose $a$ from ${2, ldots, n - 1}$ uniformly at random
return ‘Prime’ if $[a^{n-1} = 1] (text{mod} n)$ and ‘Composite’ otherwise
For a Carmichael number, this test incorrectly returns ‘Prime’ if and only if $a$ and $n$ are coprime, i.e. with probability
$frac{varphi(n)-1}{n - 2}$. In textbooks, it is suggested that this number is far too high to use Fermat's test as a prime test for a Carmichael number, but I was wondering if there are any good concrete bounds for this probability that support this claim.
number-theory prime-numbers totient-function pseudoprimes carmichael-numbers
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
$endgroup$
add a comment |
$begingroup$
Short version: I am wondering if there are any good bounds of the form $phi(n) geq f(n)cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number.
Long version: Consider Fermat's test in the following form for an odd integer $n>2$:
choose $a$ from ${2, ldots, n - 1}$ uniformly at random
return ‘Prime’ if $[a^{n-1} = 1] (text{mod} n)$ and ‘Composite’ otherwise
For a Carmichael number, this test incorrectly returns ‘Prime’ if and only if $a$ and $n$ are coprime, i.e. with probability
$frac{varphi(n)-1}{n - 2}$. In textbooks, it is suggested that this number is far too high to use Fermat's test as a prime test for a Carmichael number, but I was wondering if there are any good concrete bounds for this probability that support this claim.
number-theory prime-numbers totient-function pseudoprimes carmichael-numbers
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
$endgroup$
2
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
1
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16
add a comment |
$begingroup$
Short version: I am wondering if there are any good bounds of the form $phi(n) geq f(n)cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number.
Long version: Consider Fermat's test in the following form for an odd integer $n>2$:
choose $a$ from ${2, ldots, n - 1}$ uniformly at random
return ‘Prime’ if $[a^{n-1} = 1] (text{mod} n)$ and ‘Composite’ otherwise
For a Carmichael number, this test incorrectly returns ‘Prime’ if and only if $a$ and $n$ are coprime, i.e. with probability
$frac{varphi(n)-1}{n - 2}$. In textbooks, it is suggested that this number is far too high to use Fermat's test as a prime test for a Carmichael number, but I was wondering if there are any good concrete bounds for this probability that support this claim.
number-theory prime-numbers totient-function pseudoprimes carmichael-numbers
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
$endgroup$
Short version: I am wondering if there are any good bounds of the form $phi(n) geq f(n)cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number.
Long version: Consider Fermat's test in the following form for an odd integer $n>2$:
choose $a$ from ${2, ldots, n - 1}$ uniformly at random
return ‘Prime’ if $[a^{n-1} = 1] (text{mod} n)$ and ‘Composite’ otherwise
For a Carmichael number, this test incorrectly returns ‘Prime’ if and only if $a$ and $n$ are coprime, i.e. with probability
$frac{varphi(n)-1}{n - 2}$. In textbooks, it is suggested that this number is far too high to use Fermat's test as a prime test for a Carmichael number, but I was wondering if there are any good concrete bounds for this probability that support this claim.
number-theory prime-numbers totient-function pseudoprimes carmichael-numbers
number-theory prime-numbers totient-function pseudoprimes carmichael-numbers
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
asked Feb 1 at 16:39
Manuel EberlManuel Eberl
404210
404210
2
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
1
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16
add a comment |
2
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
1
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16
2
2
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
1
1
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16
add a comment |
0
active
oldest
votes
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%2f3096453%2flower-bounds-for-totient-function-of-a-carmichael-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3096453%2flower-bounds-for-totient-function-of-a-carmichael-number%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
2
$begingroup$
There appear to be many Carmichael numbers divisible by $7$, and for those $phi(n)leq frac{6}{7}n$.
$endgroup$
– Wojowu
Feb 1 at 16:48
1
$begingroup$
If the given $n$ is a Carmichael-number with $3$ distinct large prime factors, then , the probability that the test fails, is almost $1$. We have a better situation, when th Carmichael number has many small prime factors. But since the first step to test the primality of a number is checking for small prime factors, this case is of little practical interest. In the case, you want to improve the Fermat-test, google strong-Fermat-test, which is only slightly more complicated and much more reliable.
$endgroup$
– Peter
Feb 2 at 11:45
$begingroup$
No, I'm really just interested in evaluating how bad the error probability is. I was hoping for something like ‘$phi(n)/n$ is close to 1 for all/most Carmichael numbers $n$’, but what you said about it being close to 1 unless it has large prime factors and the case of small factors being uninteresting anyway does make sense. Thanks!
$endgroup$
– Manuel Eberl
Feb 2 at 18:59
$begingroup$
Of course, then it would be interesting to know just how many Carmichael numbers with few and big prime factors there are. But I suppose that's difficult to quantify.
$endgroup$
– Manuel Eberl
Feb 2 at 19:01
$begingroup$
Often, for the random base $a$ with $1<a<n$ , it is first checked whether $ gcd(a,n)ne 1 $, in which case we have found a non-trivial factor. In this sense, Carmichael numbers will fail with probability $1$.
$endgroup$
– Peter
Feb 3 at 8:16