THE HIDDEN NUMBER PROBLEM WITH NON-PRIME MODULUS
We consider a generalization of the Hidden Number Problem forgeneral moduli N, and prove that it can be solved with high probabilityif roughly approximations of quality at least are given, and the multipliers are chosen uniformly at random from We prove a similar result in the case that the multipliers are chosen uniformly at random from and N is the product of two distinct primes. The last result holds in the more general case when N is squarefree and a technical condition related to the prime factors of N holds. The condition is related to the distribution of the solutions of a linear equation modulo N. The Hidden Number Problem modulo the product of two primes, with multipliers chosen from is related to the bit security of the most significant bits of the RSA and Rabin functions. Our solution of the Hidden Number Problem implies that computing roughly bits of the RSA and Rabin functions is equivalent to computing the entire values.
hidden number problem, exponential sums, lattice basis reduction.