Algorithm for Generating Primes p and q Such that q Divides p 4 ± p 3 + p 2 ± p + 1

Abstract

In the paper we propose an algorithm for generating large primes p and q such that q divides p₄ + p₃ + p₂ + p + 1 or p₄ − p₃ + p₂ − p + 1, and p, q are key parameters for Giuliani-Gong's Public Key System. We analyze the computational complexity of considered methods.