Abstract. In this paper we consider the difficulty of factoring multivariate polynomials F(x, y,z,...) modulo n. We consider in particular the case in which F is a product of two randomly chosen polynomials P and Q with algebraically specified coefficients, and n is the product of two randomly chosen primes p and q. The general problem of factoring F is known to be at least as hard as the factorization of n, but in many restricted cases (when P от Q are known to have a particular form) the problem can be much easier. The main result of this paper is that (with one trivial exception), the problem of factoring F is at least as hard as the factorization of n whenever P and Q are randomly chosen from the same sample space, regardless of what may be known about its form.
1. Introduction
If you pick two random primes p and q and multiply them together, the result is believed to be very difficult to factor. Even though this complexity is unproven (both in the worst case sense and in the average case sense), this widely accepted assumption serves as a basis for the security of several cryptographic schemes (such as the RSA — see Rivest, Shamir and Adleman [1978]).
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct commercial advantage, the ACM copyright notice and the
title of the publication and its date appear, and notice is given
that copying is by permission of the Association for Computing
Machinery. To copy otherwise, or to republish, requires a fee
and/or specific permission.
25th ACM STOC '93-5/93/CA,USA
e 1993 ACM 0-89791-591-7/93/0005/0796...$1.50
In this paper we consider the following related problem: If you pick two random multivariate polynomials P(x,y,z,...) and Q(x,y,z,...) and multiply them together, is the result hard to factor? We are interested in particular in the case where the polynomial product F = PQ is computed modulo a numeric product n = pq, and try to relate the difficulty of factoring F with the difficulty of factoring n.
Our interest in this problem arose in an attempt to construct new cryptographic schemes, which are more efficient than the RSA. They are based on the problem of factoring multivariate polynomials modulo a composite n, and we were surprised to discover that this natural problem received little attention in the literature. There are many papers on the problems of factoring such polynomials over Z, Q, or over finite fields, but not over rings such as Zn. It is easy to prove that in the worst case the problem of factoring F cannot be easier than the problem of factoring n, but there seems to be no analysis of:
1. The average case complexity of the problem (F may be easy to factor for random choices of P and Q).
2. The problem of factoring multivariate polynomials of particular forms (e.g., when only certain monomials appear in the given polynomial F).
3. The problem of factoring multivariate polynomials when side information is available (e.g., that the unknown factors P and Q have a particular form).
All these problems arise naturally in cryp-
