15.02.2007

A Decentralized Test for Primality

In this talk we will present a new, fully decentralized version of the Solovay-Strassen test for integer primality. Here, decentralized means with no trusted server, no trusted party at all. All the computations can be performed in such a way that the participants (agents, parties) collectively generate a very large integer to be tested while each of them does know only his individual share of the tested integer. No one gets the tested number, it is never revealed. The protocol returns the PRIME/COMPOSITE answer. To this end, we will introduce fully decentralized procedures for checking equality of two integers, "less than" relation, and calculating many other number theoretic relations and functions, including the Legendre and Jacobi symbols.