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

Question

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

Answer 1

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