A secret bit decomposition device, wherein it is assumed that p denotes a Mersenne prime number, m denotes an integer that satisfies a relation m ≤ 2 u, a boundary value u that is a natural number is denoted as ┌logm┐, i denotes an integer from 0 to m-1, j denotes an integer from 0 to m-1, denotes an operator that converts whether any proposition P is true or false into an integer, a linear secret sharing value of a plain text a is denoted as [a], a duplicate secret sharing value of the plain text a is denoted as {a}, the plain text a is an integer that is equal to or greater than 0 and smaller than a modulo p and satisfies a relation a ≡ 2 u 0, and the plain text a is expressed as a sum of m sub-shares x 0,..., x m-1 as a ≡ p ∑ i < m x i, and the secret bit decomposition device is characterized by comprising: a public value multiplying secret computation part that, under a condition that 2 u a < p, is adapted to obtain a duplicate secret sharing value {a} Zp and to compute a transformed secret sharing value {a'} Zp (= 2 u × Zp {a} Zp) by a secret computation of public value multiplication; a lower bit distribution part that is adapted to determine a lower bit sharing value r i Z 2 u by distributing u bits beginning with a 0-th bit of a j-th sub-share {a'} Zp <j> of the transformed secret sharing value for all i that satisfies a condition that i < m; a higher bit distribution part that is adapted to determine a higher bit sharing value q i Z 2 l by distributing I bits beginning with an u-th bit of the j-th sub-share {a'} Zp <j> of the transformed secret sharing value for all i that satisfies a condition that i < m; a lower bit addition part that is adapted to compute a lower bit sum value ∑ i < m r i Z 2 u Z 2 2 u by a secret computation by an adding circuit, it being assumed that lower u bits of the lower bit sum value is denoted as r u Z 2 u, and higher u bits of the lower bit sum value is denoted as q u Z 2 u a zero determination part that is adapted to obtain the lower u bits of the lower bit sum value and to compute a zero determination value [[r u ≠ 0]] Z2 by a secret computation by a zero determining circuit; and a higher bit addition part that is adapted to obtain the higher bit sum value, the higher u bits of the lower bit sum value and the zero determination value for all i that satisfies a condition that i < m, to compute a sequence of secret sharing bit values by a secret computation by the adding circuit, and to output the computation result. a public value multiplying secret computation part that, under a condition that 2 u a < p, is adapted to obtain a duplicate secret sharing value {a} Zp and to compute a transformed secret sharing value {a'} Zp (= 2 u × Zp {a} Zp) by a secret computation of public value multiplication; a lower bit distribution part that is adapted to determine a lower bit sharing value r i Z 2 u by distributing u bits beginning with a 0-th bit of a j-th sub-share {a'} Zp <j> of the transformed secret sharing value for all i that satisfies a condition that i < m; a higher bit distribution part that is adapted to determine a higher bit sharing value q i Z 2 l by distributing I bits beginning with an u-th bit of the j-th sub-share {a'} Zp <j> of the transformed secret sharing value for all i that satisfies a condition that i < m; a lower bit addition part that is adapted to compute a lower bit sum value ∑ i < m r i Z 2 u Z 2 2 u by a secret computation by an adding circuit, it being assumed that lower u bits of the lower bit sum value is denoted as r u Z 2 u, and higher u bits of the lower bit sum value is denoted as q u Z 2 u a zero determination part that is adapted to obtain the lower u bits of the lower bit sum value and to compute a zero determination value [[r u ≠ 0]] Z2 by a secret computation by a zero determining circuit; and a higher bit addition part that is adapted to obtain the higher bit sum value, the higher u bits of the lower bit sum value and the zero determination value for all i that satisfies a condition that i < m, to compute a sequence of secret sharing bit values by a secret computation by the adding circuit, and to output the computation result.