RSA算法密鑰生成

Question

我目前正在努力與RSA encryption algorythm。

我的問題是位於public/private密鑰生成，這裏是我的步驟：

1. -Generate 2 prime numbers p, q with p > q and nbBits(p) == nbBits(q) 
      using the miller-rabin algorythm this was done succesfully 
2. -compute n = p*q 
3. -compute fi(n) = (p-1)*(q-1) 

來了麻煩：我需要找到一個整數e與q < e < fi(n)。這個整數需要某種素數。

我的問題是：e是否必須是原始的（不能被任何數字除以它自己或1）或原始的WITH fi(n) (gcd(e, fi(n)) = 1)或兩者？

我真的有一些問題搞清楚了這一點（我的源代碼中明確指出需要對歐幾里德algorythm（GCD），但因爲英語不是我的母語，我有一些麻煩與數學英語）

可能是一個愚蠢的問題，但我找不到明確的解釋（至少對我來說足夠清楚）。

感謝您的閱讀，甚至更多的回答。

Answer 1

加密指數e需要與phi(n)互斥，即gcd(e,phi(n)) = 1。 這個條件是必要的，否則，你將無法構造（通過Euclid的擴展算法）指數d（解密指數），使得e*d = 1 mod phi(n)。