  Primality generation is the cornerstone of several essential cryptographic
systems. The problem has been a subject of deep investigations, but there is
still a substantial room for improvements. Typically, the algorithms used have
two parts trial divisions aimed at eliminating numbers with small prime factors
and primality tests based on an easy-to-compute statement that is valid for
primes and invalid for composites. In this paper, we will showcase a technique
that will eliminate the first phase of the primality testing algorithms. The
computational simulations show a reduction of the primality generation time by
about 30% in the case of 1024-bit RSA key pairs. This can be particularly
beneficial in the case of decentralized environments for shared RSA keys as the
initial trial division part of the key generation algorithms can be avoided at
no cost. This also significantly reduces the communication complexity. Another
essential contribution of the paper is the introduction of a new one-way
function that is computationally simpler than the existing ones used in
public-key cryptography. This function can be used to create new random number
generators, and it also could be potentially used for designing entirely new
public-key encryption systems.
