On the number of solutions of the equation Rx 2 + Sy 2 = 1 (mod N)

Boneh, D., Gentry, C. and Hamburg, M. (2007). Space-efficient identity based encryption without pairings. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE Computer Society, Providence, RI, 647–657. Full version is available at http://crypto.stanford.edu/~dabo/ .

Cocks, C. (2001). An identity based encryption scheme based on quadratic residues. In Cryptography and Coding, (B. Honary, ed.). Lecture Notes in Comput. Sci., 2260. Springer, Berlin, 360–363.

Cremona, J.E. and Rusin, D. (2003). Efficient solution of rational conics. Math. Comp., 72, 1417–1441.

Ireland, K. and Rosen, M. (1990). A Classical Introduction to Modern Number Theory. Second Edition. Graduate Texts in Mathematics, 84. Springer-Verlag, New York.

Jhanwar, M. and Barua, R. (2009). A semantically secure public key encryption in the standard model. In Preproceedings of the International Workshop on Coding and Cryptography (WCC’09), 181–190.

Ong, H., Schnorr, C.P. and Shamir, A. (1984). An efficient signature scheme based on quadratic equations. Proc. 16th Annual ACM Symposium on Theory of Computing (STOC’84), 208–216.

Pollard, J. M. and Schnorr, C. P. (1987). An efficient solution of the congruence x 2 + ky 2 = m (mod n), IEEE Trans. Inform. Theory. 33, 702–709.