Here's an interesting application of 4Squares: creating 'trap doors' in RSA encryption. http://www.moi.math.bas.bg/oc2009/a26.pdf Hiding information in products of integers. Constantinos Patsakis, Nikolaos Alexandris {kpatsak, alexandr}@unipi.gr Department of Informatics, University of Piraeus Karaoli & Dimitriou 80, Piraeus, 185 34 Greece Sixth International Workshop on Optimal Codes and Related Topics June 16-22, 2009, Varna, Bulgaria pp. 157-162 Abstract. In this work we present a new SETUP for public key encryption algorithms that use products as part of their keys. Using the decomposition of an integer as a *** sum of four squares, *** enables us to create a backdoor on the products that if properly used, may lead their polynomial time factorization. At 10:24 PM 4/30/2013, Fred lunnon wrote:

Henry Baker has raised the matter of deterministic algorithms for square-root (mod p) .

The Bumby paper seems to have been published in the late 1980's, after a burst of activity in this area. There does not appear to have been much progress since: a 2010 paper by Tsz-Wo Sze at arxiv.org/pdf/0812.2591 implies that there is no known deterministic algorithm in time polynomial in log(p).

WFL