Algorithms for Relatively Cyclotomic Primes

Article type: Research Article

Authors: Grześkowiak, Maciej

Affiliations: Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland. maciejg@amu.edu.pl

Note: [] The author was partially supported by the grant no. N N201 605940 from National Science Centre.

Abstract: We present a general method of generating primes p and q such that q divides Φn(p), where n > 2 is a fixed number. In particular, we present the deterministic method of finding a primitive nth roots of unity modulo q. We estimate the computational complexity of our methods.

Keywords: primes of a special form, computing a primitive nth root of unity modulo primes, public key cryptography

DOI: 10.3233/FI-2013-858

Journal: Fundamenta Informaticae, vol. 125, no. 2, pp. 161-181, 2013