My question is regarding the notes pages 1-2 specifically http://www.cs.berkeley.edu/~sinclair/cs271/n3.pdf
I understand everything up to the point near the top of the second page where it says
"The numbers transmitted in the above protocol are integers $\mathrm{mod}\;p$, where $p = O(n).$ Hence the number of bits transmitted is only $O(\mathrm{log}\; n)$, an exponential improvement over the deterministic scenario."
I'm confused as to what they mean here. If $p$ is a prime picked from $\{2,...,T\}$ then i understand $p=O(n)$ since $T=O(n)$ as $T=cn$. Firstly i'm not sure if this is what they mean when they say $p=O(n)$. Secondly i'm not sure what they mean when they say the number of bits being transmitted is only $O(\mathrm{log}\; n)$.
I'd really appreciate any clarification.
You are right with the reasoning why $p=O(n)$. Now recall that we refrain from transmitting the $n$-bit numbers $a$ or $b$ and instead transmit the number $F_p(a)$, which is a number $<p<cn$ and hence can be transmitted using $\log_2(c n)=O(\log n)$ bits. Compare also the example, where $32$ bit fingerprints are used for about a megabyte of original data.