A method and system for distributing a secret are described. In one embodiment, the secret is represented by a secret polynomial of degree d over GF(q) constructed with a prime or a power of a prime. The secret polynomial is then embedded into an extension polynomial of degree m that is greater than d. The extension polynomial is divided by n coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate n shares of the secret. Each share includes one of the divisor polynomials and a corresponding remainder. These n shares are distributed among a plurality of cooperating entities for secret sharing.