# RSA - statements re $\phi(n)$, $\lambda(n)$ and $n$, given $n$,$|n|=1024bits$, and $e=65537$

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)$$.
• 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$. – Derek Holt Apr 22 at 19:40
• 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. – Kolja Apr 22 at 19:41
• Ok thank you both. I have updated the information above. Now I am looking for information for the revised second question. – unseen_rider Apr 22 at 20:02
• Any thoughts about the answer I posted two days ago, unseen? – Gerry Myerson Apr 25 at 5:33
• @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? – unseen_rider Apr 25 at 21:58

$$\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)$$.