Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE.
Why does he require that and how this effect the proof of lemma 4.2?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
He needs to add something uniformly random to the second coordinate, to get a distribution that is uniformly random. (The idea is that if he guesses the correct key, his rerandomization turns real instances into real instances. If he guesses the wrong key, his rerandomization should turn real instances into random instances.)
If $p$ is a prime, then multiplication by any non-zero value is a bijection, so a uniformly distributed $l$ maps to a uniformly distributed product $l(k-s_1)$.
If $p$ is composite, then multiplication by a value that isn't relatively prime to $p$ would not be a bijection, so a uniformly distributed $l$ might not map to a uniformly distributed product $l(k-s_1)$.