2
$\begingroup$

Assume $n=pq$, with $p,q$ primes, $e=65537$, and length of $n$, $|n|=N=1024$ bits = 309 decimal digits. $p,q$ are unknown.

I am trying to understand the information sourced from Wikipedia page on RSA better. This is not a homework question.

I assume from Wikipedia that $\phi(N)$ equals the order of the multiplicative group $Z_N^*$.

Now by definition of Euler's totient function $\phi(N)$ is also equal to $1024(1-\frac{1}{2})=512$ since $2$ is the only prime which divides $1024$.

Also $\lambda(n)=LCM(p-1,q-1)$.

Wikipedia page states $\lambda(n) | \phi(n)$, and $\phi(n) = (p-1)(q-1)$

Questions:

  1. This would mean that $512=\phi(n) \ge \lambda(n) > e = 65537$ which can't be right. Am I misunderstanding something? - Corrected assumption & now resolved

  2. What information can we deduce about $n$, $\phi(n)$ or $\lambda(n)$ - eg can we obtain a lower bound on $\phi(n)$? Eg $\phi(n)=(p-1)(q-1) \ge \lambda(n) > e = 65537$ ?

    • I'm looking for useful info / ways how to reduce numbers to consider for $\phi(n)$ and $\lambda(n)$.
$\endgroup$
  • 1
    $\begingroup$ Your remark that $\phi(n) = 512$ is not true. $n$ is a number with about $1024$ bits. In fact $\phi(n) = (p-1)(q-1)$, so yes it is true that $\phi(n) \ge \lambda(n)$. Since $p$ and $q$ are numbers with roughly $512$ bits, they are considerably larger than $e$. $\endgroup$ – Derek Holt Apr 22 at 19:40
  • $\begingroup$ You used $\phi(N)$ in stead of $\phi(n)$. The number $n$ has 309 decimal digits. It's pretty big. On the other hand $N$ is the number of (binary) digits of $n$. $N$ is just a rough estimate for $n$. There are MANY numbers with $N$ digits. $\endgroup$ – Kolja Apr 22 at 19:41
  • $\begingroup$ Ok thank you both. I have updated the information above. Now I am looking for information for the revised second question. $\endgroup$ – unseen_rider Apr 22 at 20:02
  • $\begingroup$ Any thoughts about the answer I posted two days ago, unseen? $\endgroup$ – Gerry Myerson Apr 25 at 5:33
  • $\begingroup$ @gerrymyerson yes helpful. I am planning to use results in your answer for a brute force algorithm for RSA. Any other results on $n$, $\phi(n)$, or $\lambda(n)$ that I could use? $\endgroup$ – unseen_rider Apr 25 at 21:58
1
$\begingroup$

$\phi(n)=(p-1)(q-1)=pq-(p+q)+1=n+1-(p+q)$ so a lower bound on $\phi(n)$ comes from an upper bound on $p+q$ over all pairs with $pq=n$. This occurs when $p=2$ and $q=n/2$, so $$\phi(n)\ge(n-2)/2$$ for $n$ of the form $pq$ with $p,q$ prime.

For $\lambda(n)$, the extreme case occurs when $p-1=2(q-1)$.

$\endgroup$

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.