A New Distributed Primality Test for Shared RSA Keys using Quadratic Fields

In the generation method for RSA-moduli proposed by Boneh and Franklin in [BF97] the partial signing servers generate random shares p i ; q i and compute as candidate for an RSA-modulus n = pq where p = ( p i ) and q = ( q i ). Then they perform a time-consuming distributed primality test which simultaneously checks the primality both of p and q by computing g = 1 mod n. The primality test proposed in [BF97] cannot be generalized to products of more than two primes. A more complicated one for products of three primes was presented in [BH98]