changed 4 years ago  
Linked with GitHub

Modular Subset Product Problem

The problem

Given a list of primes, e.g., from 2 to nth prime, denoted as \(P = \{ p_0, p_1, \cdots, p_{n-1}\}\), and an integer \(X\) and a prime \(q\). To find a \(n\) bits vector \(x \in \{0, 1\}^n\), such that:

\[\prod p_i^{x_i} \equiv X \pmod{q}\]

Your works

  • Write a Sage (Python) program to solve the MSP problem. For example, we let the parameters \(n = 40\), \(X = 4462431763815383677508\) and \(q = 10396403247585105914591\).
  • Anaylize the efficience of your progrm, and try to improve.
  • What is the relation between Subset Sum Problem(SSP) and Subset Product Problem?
  • How hard is the MSP problem? Give a postulate, and prove. (I don't think you can do it.)
Select a repo