A set A is said to be invertibly paddable if there are two polynomial time computable functions pad and decode such that () xA if and only if pad (x, y) A, and () decode (pad (x, y)) y. We consider three number theoretical problems that are used in certain cryptosystems (decision of quadratic residuosity, computation of discrete logarithm and computation of Euler's totient function), and show that the sets that represent these problems are invertibly paddable. These results imply that, if these sets are not in P, then they have complexity cores C such that neither C not the complement of C are sparse.

We study the computational power of PC=P. We give a characterization of the class via single Turing machines. Based on the characterization, we give combinatorial problems that are Pm-complete for the class.

After Diffie and Hellman's paper, there have been published many cryptosystems, where large composite numbers are used as the public keys, and the factorization of them are used as the secret keys. But, on the other hand, there also have been published many integer-factoring algorithms that factor composite numbers rapidly. So methodologies to construct primes that are strong for such algorithms are needed to guarantee the safety of such cryptosystems. Here we propose a randon polynomial time algorithm for constructing strong primes that uses a probabilistic primality testing algorithm.