Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here

This is a homework problem I am trying to do. I have done part 2i) as well as 2ii) and know how to do the rest. I am stuck on 2iii) and 2vii). I truly dont know 2vii because it could be some special case I am not aware of. As for 2iii) I tried to approach it the same way as I did 2ii in which case I said you could take the 2 equations and use substitution method to isolate each variable and plug it in to find your variable values but 2iii) that doesnt work so I dont know how to do it.

share|cite|improve this question
up vote 1 down vote accepted

For $s$ sufficiently small, we can go from $b^2=n+s^2$ to $b^2\approx n$. Take the square root and you approximately have the average of $p$ and $q$. Since $s$ is small so is their difference (relatively), so we can search around $\sqrt{n}$ for $p$ or $q$. The part (iv) means absolute difference and should have written that. Take the square root of your number and you will find $p$ and $q$ very close nearby.

For (vii), say cipher and plaintexts are equal, so $m\equiv m^e$ modulo $n$. There are only a certain # of $m$ that allow this: those with $m\equiv0$ or $1$ mod $n$ or $p|m$ and $q|(m-1)$ or vice-versa, by elementary number theory. If the scheme uses padding to avoid these messages, then no collision is possible between plain and cipher, but otherwise if you allow arbitrary numbers as messages it clearly is.

share|cite|improve this answer
thanks anon! you saved my neurons again! – Raynos Mar 4 '12 at 15:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.