3
$\begingroup$

I need to calculate the number of possible public keys.

The tuple for the public key is defined as: $Key_{Publ} = (n,a)$

So: Let $p:=83$ and $q:=163$

$n= p \cdot q = 83 \cdot 163 = 13529$

$\phi(n) = (p -1 )(q - 1) =(83 - 1)(163 - 1) = 13284$

Question: How is it possible to calculate the number of possible $a$'s in $\gcd(a , \phi(n))$ with $a \in [1, \phi(n)]$ ? So I will be able to calculate the possibilities with $n \cdot a$?

I have two possible ways to calculate $\phi(n):$ $$\phi(n)=(p-1)(q-1)$$ $$\phi(n)=\prod_{p \in \mathbb P}(p^{v_p(n)-1}(p-1))$$

I appreciate every hint.

$\endgroup$
1
  • $\begingroup$ I don't understand the Question. Can you either clarify or check you have set it down correctly? $\endgroup$
    – Joffan
    Jan 15, 2017 at 22:03

1 Answer 1

Reset to default
2
+50
$\begingroup$

Hint

$\phi(\phi(n)) $ is the number of possible keys

$\endgroup$
9
  • $\begingroup$ can you show an example how you would calculate that with the numbers $p:=83$ and $q=163$, please? $\endgroup$
    – jublikon
    Jan 30, 2017 at 22:39
  • $\begingroup$ i believe in your exercise there is a Form how to calculate $\phi(n)$ $\endgroup$
    – Mohbenay
    Jan 30, 2017 at 22:41
  • $\begingroup$ and then ? $phi(13284)=?$ That is not clear to me $\endgroup$
    – jublikon
    Jan 30, 2017 at 22:42
  • 1
    $\begingroup$ exactly , now that you have 13428 = $ 2^{2} 3^{4} 41 $ you can now find $\phi(13428)$ =$ 2^{(2-1)}*(2-1)*3^{(4-1)}*(3-1)*41^{(1-1)}*(41-1) = 2*3^{3}*2*40 = 4320$ $\endgroup$
    – Mohbenay
    Jan 30, 2017 at 23:01
  • 1
    $\begingroup$ p is Prime number so in our care is 2 or 3 or 41 $v_{p}(n) $ is like $v_{2}(13284) =2$ and $v_{3}(13284) =4$ and $v_{41}(13284)=1$ $\endgroup$
    – Mohbenay
    Jan 30, 2017 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.