Mixing
How do I compute Euler phi function efficiently for repeated prime factors?
$begingroup$
In RSA decryption problems, you have to compute $phi(n)$ and then sometimes $phi(phi(n))$ quickly. For example, I had to compute $phi(2^5)$ for one particular problem and it seems to me (for example in testing situations) that there has to be some kind of algorithm to calculate this since you can't just use the property that $phi(x) = x-1$ for x prime.
number-theory cryptography
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
$endgroup$
add a comment |
$begingroup$
In RSA decryption problems, you have to compute $phi(n)$ and then sometimes $phi(phi(n))$ quickly. For example, I had to compute $phi(2^5)$ for one particular problem and it seems to me (for example in testing situations) that there has to be some kind of algorithm to calculate this since you can't just use the property that $phi(x) = x-1$ for x prime.
number-theory cryptography
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
$endgroup$
$begingroup$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39
add a comment |
$begingroup$
In RSA decryption problems, you have to compute $phi(n)$ and then sometimes $phi(phi(n))$ quickly. For example, I had to compute $phi(2^5)$ for one particular problem and it seems to me (for example in testing situations) that there has to be some kind of algorithm to calculate this since you can't just use the property that $phi(x) = x-1$ for x prime.
number-theory cryptography
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
$endgroup$
In RSA decryption problems, you have to compute $phi(n)$ and then sometimes $phi(phi(n))$ quickly. For example, I had to compute $phi(2^5)$ for one particular problem and it seems to me (for example in testing situations) that there has to be some kind of algorithm to calculate this since you can't just use the property that $phi(x) = x-1$ for x prime.
number-theory cryptography
number-theory cryptography
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
asked Apr 15 '14 at 1:28
Arthur ColléArthur Collé
7201930
7201930
$begingroup$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39
add a comment |
$begingroup$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39
$begingroup$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
According to this Wikipedia page, given any prime number $p$, $phi(p^k) = p^{k-1} cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $phi(m cdot n) = phi(m) cdot phi(n)$.
So, write the number's prime factorization as ${p_1}^{k_1} cdot {p_2}^{k_2} cdot cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) cdot {p_2}^{k_2 - 1} (p_2 - 1) cdot cdots$.
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
$endgroup$
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
add a comment |
$begingroup$
Find all prime factors of $n$, then compute
$$phi(n) = nprod_{p|n}(1-frac{1}{p})$$
where the product is over $n$'s prime factors.
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
$endgroup$
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
add a comment |
Your Answer
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%2f754175%2fhow-do-i-compute-euler-phi-function-efficiently-for-repeated-prime-factors%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$
According to this Wikipedia page, given any prime number $p$, $phi(p^k) = p^{k-1} cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $phi(m cdot n) = phi(m) cdot phi(n)$.
So, write the number's prime factorization as ${p_1}^{k_1} cdot {p_2}^{k_2} cdot cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) cdot {p_2}^{k_2 - 1} (p_2 - 1) cdot cdots$.
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
$endgroup$
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
add a comment |
$begingroup$
According to this Wikipedia page, given any prime number $p$, $phi(p^k) = p^{k-1} cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $phi(m cdot n) = phi(m) cdot phi(n)$.
So, write the number's prime factorization as ${p_1}^{k_1} cdot {p_2}^{k_2} cdot cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) cdot {p_2}^{k_2 - 1} (p_2 - 1) cdot cdots$.
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
$endgroup$
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
add a comment |
$begingroup$
According to this Wikipedia page, given any prime number $p$, $phi(p^k) = p^{k-1} cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $phi(m cdot n) = phi(m) cdot phi(n)$.
So, write the number's prime factorization as ${p_1}^{k_1} cdot {p_2}^{k_2} cdot cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) cdot {p_2}^{k_2 - 1} (p_2 - 1) cdot cdots$.
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
$endgroup$
According to this Wikipedia page, given any prime number $p$, $phi(p^k) = p^{k-1} cdot (p - 1)$, and given two coprime numbers $m$ and $n$, $phi(m cdot n) = phi(m) cdot phi(n)$.
So, write the number's prime factorization as ${p_1}^{k_1} cdot {p_2}^{k_2} cdot cdots$, and its totient is ${p_1}^{k_1 - 1} (p_1 - 1) cdot {p_2}^{k_2 - 1} (p_2 - 1) cdot cdots$.
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
answered Apr 15 '14 at 1:36
Tanner SwettTanner Swett
4,3441739
4,3441739
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
add a comment |
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Note that computing the phi function may be prohibitively difficult if you don't know the number's prime factorization. If $p$ and $q$ are prime numbers, and we know what $pq$ and $phi(pq)$ are, we can find what $p$ and $q$ are.
$endgroup$
– Tanner Swett
Apr 15 '14 at 1:39
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
$begingroup$
Wow $phi(2^k) = p^(k-1)*(p-1)$ is exactly what I was looking for, what an amazing equality.
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:42
add a comment |
$begingroup$
Find all prime factors of $n$, then compute
$$phi(n) = nprod_{p|n}(1-frac{1}{p})$$
where the product is over $n$'s prime factors.
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
$endgroup$
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
add a comment |
$begingroup$
Find all prime factors of $n$, then compute
$$phi(n) = nprod_{p|n}(1-frac{1}{p})$$
where the product is over $n$'s prime factors.
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
$endgroup$
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
add a comment |
$begingroup$
Find all prime factors of $n$, then compute
$$phi(n) = nprod_{p|n}(1-frac{1}{p})$$
where the product is over $n$'s prime factors.
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
$endgroup$
Find all prime factors of $n$, then compute
$$phi(n) = nprod_{p|n}(1-frac{1}{p})$$
where the product is over $n$'s prime factors.
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
edited Feb 3 at 5:52
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
answered Apr 15 '14 at 1:36
user2357112user2357112
2,2131914
2,2131914
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
add a comment |
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
… over $n$'s prime factors.
$endgroup$
– Wolfgang Kais
Feb 3 at 1:32
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
$begingroup$
@WolfgangKais: Yup. Thanks for pointing that out.
$endgroup$
– user2357112
Feb 3 at 5:52
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%2f754175%2fhow-do-i-compute-euler-phi-function-efficiently-for-repeated-prime-factors%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$
Do you have the prime factorization? And are you an attacker, or do you have the necessary key?
$endgroup$
– user2357112
Apr 15 '14 at 1:31
$begingroup$
I am the attacker
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:31
$begingroup$
(e,n) = (17, 323) and the ciphertext was 185 but I was trying to keep the question general so that I could learn the underlying way to quickly compute $phi(n)$ in a variety of problems
$endgroup$
– Arthur Collé
Apr 15 '14 at 1:32
$begingroup$
For the product $pq$ of two large primes, finding $varphi(pq)$ is "just as difficult" as factorization. If we know $varphi(pq)$, we can easily compute $p$ and $q$.
$endgroup$
– André Nicolas
Apr 15 '14 at 1:39