Miyaji, Nakabayashi, and Takano proposed the algorithm for the construction of prime order pairing-friendly elliptic curves with embedding degrees $k=3,4,6$. We present a method for generating generalized MNT curves. The order of such pairing-friendly curves is the product of two prime numbers.

We present a method of generating primes r ≡ 1 (mod n), q and a Weil q-number π such that r divides Φ n ( q) and r divides | A(𝔽 q )|, where A/𝔽 q is an ordinary abelian variety defined over a finite 𝔽 q corresponding to π. Such primes can be used for implementing pairing-based cryptographic systems.

Given a square-free integer Δ < 0, we present an algorithm constructing a pair of primes p and q such that q|p + 1 − t and 4p − t 2 = Δf 2 , where |t| ≤ 2√p for some integers f, t. Together with a CM method presented in the paper, such primes p and q are used for a construction of an elliptic curve E over a finite field $\mathbb{F}_p$ such that the order of E is divisible by a large prime. It is shown that our algorithm works in polynomial time.

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.

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