RANDOM NUMBER GENERATION APPARATUS, RANDOM NUMBER GENERATION METHOD AND PROGRAM

Abstract

A random number acquiring unit 15 obtains a first sequence that comprises values of digits of a random number represented by a binary number as elements. A logical product arithmetic unit 16 obtains a third sequence that is results of elementwise logical product operation between the first sequence and a second sequence that comprises values of digits of one or more Mersenne numbers represented by one or more binary numbers and a zero value as elements.

Claims

1: A random number generation apparatus comprising: a random number acquiring unit obtaining a first sequence that comprises values of digits of a random number represented by a binary number as elements; and a logical product arithmetic unit obtaining a third sequence that is results of elementwise logical product operation between the first sequence and a second sequence that comprises values of digits of one or more Mersenne numbers represented by one or more binary numbers and a zero value as elements.

2: The random number generation apparatus according to claim 1, wherein the first sequence comprises a first subsequence; a second subsequence comprised in the second sequence indicates any of the Mersenne numbers; the third sequence comprises a third subsequence that is results of elementwise logical product operation between the first subsequence and the second subsequence; and the processes of the random number acquiring unit and the logical product arithmetic unit are executed again when the second subsequence matches the third subsequence.

3: The random number generation apparatus according to claim 1, wherein the first sequence comprises a first subsequence; a second subsequence comprised in the second sequence indicates any of the Mersenne numbers; the third sequence comprises a third subsequence that is results of elementwise logical product operation between the first subsequence and the second subsequence; and the processes of the random number acquiring unit and the logical product arithmetic unit are executed again when elements of the third subsequence are constituted by zeros.

4: The random number generation apparatus according to any of claims 1 to 3, wherein the second sequence comprises the values of the digits of the plurality of Mersenne numbers.

5: The random number generation apparatus according to claim 4, wherein the first sequence comprises a plurality of first subsequences; a plurality of second subsequences comprised in the second sequence indicate values of digits of the respective Mersenne numbers; the third sequence comprises a plurality of third subsequences; and the plurality of third subsequences are results of elementwise logical product operation between the respective first subsequences and the respective second subsequences; and the random number generation apparatus comprises a determiner obtaining each of a plurality of equality determination results indicating whether or not the plurality of second subsequences match the plurality of third subsequences, respectively, by a batch determination of equality; obtaining an aggregate determination result indicating whether any second subsequence and third subsequence match each other or not by a sum operation or a product operation of the plurality of equality determination results; and causing the processes of the random number acquiring unit and the logical product arithmetic unit to be executed again when the aggregate determination result indicates that any second subsequence and third subsequence match each other.

6: The random number generation apparatus according to claim 4, wherein the first sequence comprises a plurality of first subsequences; a plurality of second subsequences comprised in the second sequence indicate values of digits of the respective Mersenne numbers; the third sequence comprises a plurality of third subsequences; and the plurality of third subsequences are results of elementwise logical product operation between the respective first subsequences and the respective second subsequences; and the random number generation apparatus comprises a determiner obtaining each of a plurality of equality determination results indicating whether elements of each of the plurality of third subsequences are constituted by zeros or not by a batch determination of equality; obtaining an aggregate determination result indicating whether elements of any of the third subsequences are constituted by zeros or not by a sum operation or a product operation of the plurality of equality determination results; and causing the processes of the random number acquiring unit and the logical product arithmetic unit to be executed again when the aggregate determination result indicates that elements of any of the third subsequences are constituted by zeros.

7: The random number generation apparatus according to any of claims 1 to 3, wherein at least a part of the Mersenne numbers are Mersenne primes.

8: A random number generation method comprising: a random number acquiring step of obtaining, by a random number acquiring unit, a first sequence that comprises values of digits of a random number represented by a binary number as elements; and a logical product operation step of obtaining, by a logical product arithmetic unit, a third sequence that is results of elementwise logical product operation between the first sequence and a second sequence that comprises values of digits of one or more Mersenne numbers represented by one or more binary numbers and a zero value as elements.

9: A program for causing a computer to function as the random number generation apparatus according to any of claims 1 to 3.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0008] FIG. 1 is a block diagram illustrating a functional configuration of a random generation apparatus of embodiments;

[0009] FIG. 2A is a flow diagram illustrating a random generation method of the embodiments;

[0010] FIG. 2B is a flow diagram illustrating an equality determination process; and

[0011] FIGS. 3A to 3C are diagrams illustrating first to third sequences of the embodiments.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0012] Embodiments of the present invention will be described below.

<Outline>

[0013] In the embodiments, a random number belonging to a predetermined set is generated as described below. First, a “first sequence” which comprises values of digits of a random number represented by a binary number (a binary random number) as elements is obtained (a random number acquiring step). This random number may be a uniform random number or may not be a uniform random number. The concept of a “random number” includes a genuine random number and a pseudo-random number. The random number may be generated in advance or may be generated when the “first sequence” is obtained. The “first sequence” may comprise only the values of the digits of the random number represented by a binary number as elements or may furthermore comprise other elements. Next, a “third sequence”, which is results of elementwise logical product operation (elementwise AND operation results, for example, bit AND operation results) between the “first sequence” and a “second sequence, is obtained (a logical product operation step). Here, the “second sequence” is a sequence which comprises values of digits of one or more Mersenne numbers p.sub.i (i=0, . . . , N−1; N is an integer of 1 or more) represented by one or more binary numbers, and zero values as elements. The number of elements of the “second sequence” is, for example, the same as the number of elements of the “first sequence”. The “second sequence” may comprise only the values of the digits of the Mersenne number(s) p.sub.i and the zero values as the elements or may furthermore comprise other elements (for example, a fixed value, attribute information and the like). The Mersenne number p.sub.i is an integer which satisfies 2.sup.n(i)−1, and the Mersenne number p.sub.i represented by a binary number is a sequence 1 . . . 1 which is constituted by n(i) 1's. Here, n(i) is a particular positive integer. An example of p.sub.i is a Mersenne prime. For example, at the time of n(i)=2, 3, 5, 7, 13, 17, 19, 31, 61 or the like, p.sub.i is a Mersenne prime. The “third sequence” is a sequence obtained by masking the “first sequence” with the “second sequence” and is a sequence which comprises a random number t.sub.i with n(i) digits represented by a binary number. The random number t.sub.i can be treated as a random number on a factor ring (a residue class) modulo the Mersenne number p.sub.i. Especially, when p.sub.i is a Mersenne prime, the random number t.sub.i can be treated as a random number on a residue field (a prime field) modulo the Mersenne number p.sub.i. On the factor ring modulo the Mersenne number p.sub.i, p.sub.i, p.sub.i=2.sup.n(i)−1 and 0 are the same value (2.sup.n(i)−1 mod(2.sup.n(i)−1)=0), and N random numbers t.sub.i (i=0, . . . , N−1) comprised in the “third sequence” can be “necessarily” treated as random numbers on the factor ring modulo the Mersenne number p.sub.i. Therefore, it is possible to generate a random number on a factor ring at a higher speed in comparison with prior arts in which the random number generation probability decreases depending on an environment.

[0014] However, since p.sub.i and 0 are treated as the same value on the factor ring modulo p.sub.i (0 is an equivalence class of p.sub.i), the random number t.sub.i is not necessarily a uniform random number. That is, when the random number represented by the “first sequence” is a uniform random number, each of the probabilities of t.sub.i being 0, 1, . . . , p.sub.i is ½.sup.n(i), and the probability of t.sub.i being p.sub.i or 0 is ½.sup.n(i)−1. Therefore, on the factor ring described above, the generation probability of 0 (in other words, the generation probability of p.sub.i) is ½.sup.n(i)−1, and the generation probabilities of other random numbers are ½.sup.n(i). In order to obtain a uniform random number on the factor ring, it is only necessary to discard a generated random number and perform the random number acquiring step and the logical product operation step again when t.sub.i=p.sub.i is satisfied. In other words, the processes of the random number acquiring step and the logical product operation step can be executed again when the “first sequence” comprises a “first subsequence”, a “second subsequence” comprised in the “second sequence” indicates any Mersenne number Pi, the “third sequence” comprises a “third subsequence” which is results of elementwise logical product operation between the “first subsequence” and the “second subsequence”, and the “second subsequence” matches the “third subsequence”. In such a configuration also, the probability of t.sub.i=p.sub.i being satisfied (the probability of the “second subsequence” and the “third subsequence” matching each other) is only about ½.sup.n(i)−1, and it is possible to generate a uniform random number on a factor ring at a high speed.

[0015] Otherwise, the random number acquiring step and the logical product operation step may be performed again when t.sub.i=0 is satisfied. In other words, the processes of the random number acquiring step and the logical product operation step may be executed again when elements of the “third subsequence” are constituted by zeros (when the “third subsequence” is a zero vector). Thereby, it is also possible to generate a uniform random number on a factor ring at a high speed.

[0016] Further, when it is assumed that N is an integer of 2 or more and that the “second sequence” is a sequence which comprises values of digits of a plurality of Mersenne numbers p.sub.i represented by binary numbers, and zero values as elements, a plurality of random numbers on factor rings can be generated by parallel processes, and random number generation at a higher speed becomes possible. The numbers of digits (bit lengths) n(i) of the Mersenne numbers p.sub.i represented by binary numbers may be mutually the same or may not be the same.

[0017] In the case of generating uniform random numbers on a factor ring by such parallel processes, it is possible to (1) simultaneously determine whether t.sub.i=p.sub.i is satisfied or not for i=0, . . . , N−1 by a batch equality determination, (2) obtain an aggregate determination result x indicating, for any i, whether t=p.sub.i is satisfied or not by a sum operation or a product operation of the equality determination results x.sub.i (i=0, . . . , N−1), and (3) perform the random number acquiring step and the logical product operation step again when the aggregate determination result x indicates, for any i, that t.sub.i=p.sub.i is satisfied. In other words, (1) each of the equality determination results x.sub.i (i=0, . . . , N−1) indicating whether or not a plurality of “second subsequences” match a plurality of “third subsequences”, respectively, is obtained by the batch determination of equality, (2) an aggregate determination result x indicating whether any “second subsequence” and “third subsequence” match each other or not is obtained by a sum operation or a product operation of the plurality of equality determination results x.sub.i, and (3) when the aggregate determination result x indicates that any “second subsequence” and “third subsequence” match each other, the random number acquiring step and the logical product operation step may be executed again. Here, the “first sequence” comprises a plurality of “first subsequences”; the plurality of “second subsequences” comprised in the “second sequence” indicate values of digits of the respective Mersenne numbers p.sub.i; the “third sequence” comprises the plurality of “third subsequences”; and the plurality of “third subsequences” are results t.sub.i of elementwise logical product operation between the respective “first subsequences” and the respective “second subsequences”. Here, the operation amounts of the batch determination of equality, the sum operation and the production operation are small. Further, as described above, the probability of t.sub.i=p.sub.i being satisfied is about ½.sup.n(i)−1, and the probability of t.sub.i=p.sub.i being satisfied for any i is low. Therefore, it is possible to generate a uniform random number on a factor ring at a higher speed.

[0018] Otherwise, (4) determinations about whether t.sub.i=0 is satisfied or not are simultaneously performed for i=0, . . . , N−1 by a batch determination of equality, (5) an aggregate determination result x indicating, for any i, whether t.sub.i=0 is satisfied or not is obtained by a sum operation or a product operation of equality determination results x.sub.i (i=0, . . . , N−1) of the batch determination of equality, and (6) when the aggregate equality determination result x indicates that t.sub.i=0 is satisfied for any i, the random number acquiring step and the logical product operation step may performed again. In other words, (4) each of the plurality of equality determination results x.sub.i (i=0, . . . , N−1) indicating whether elements of each of the plurality of “third subsequences” are constituted by zeros or not is obtained by the batch determination of equality, (5) the aggregate determination result x indicating whether elements of any “third subsequence” are constituted by zeros or not is obtained by a sum operation or a product operation of the plurality of the equality determination results x.sub.i, and (6) when the aggregate determination result x indicates that elements of any “third subsequence” are constituted by zeros, the processes of the random number acquiring step and the logical product operation step may be executed again. In this case also, it is possible to generate a uniform random number on a factor ring at a high speed.

First Embodiment

[0019] Next, a first embodiment will be described. In the present embodiment, description will be made on a case where p.sub.i is a Mersenne prime.

<Configuration>

[0020] As illustrated in FIG. 1, a random number generation apparatus 1 of the present embodiment has a binary random number generator 11, storage 12, an inputting unit 13, a mask generator 14, a random number acquiring unit 15, a logical product arithmetic unit 16 and an outputting unit 18. The random number generation apparatus 1 is, for example, an apparatus configured by a general-purpose or dedicated computer provided with a processor (a hardware processor) such as a CPU (central processing unit), memories such as a RAM (random-access memory) and a ROM (read-only memory), and the like executing a predetermined program. The computer may be provided with one processor and one memory or may be provided with a plurality of processors and a plurality of memories. The program may be installed in the computer or may be recorded in the ROM or the like in advance. Further, a part or all of the processing units may be configured with the use of an electronic circuit (a circuitry) which realizes processing functions without using a program, instead of an electronic circuit which realizes a functional configuration by a program being read like a CPU. Further, the electronic circuit constituting one apparatus may comprise a plurality of CPUs.

<Process>

[0021] In the present embodiment, each of the “first sequence”, “second sequence” and “third sequence” is treated as a vector constituted by L elements, and it is assumed that the random number generation apparatus 1 performs an operation with n-bit precision. Here, L is a positive integer larger than the total number of elements n(0)+ . . . +n(N−1) of Mersenne primes p.sub.0, . . . , p.sub.N−1 represented by binary numbers. Here, L may be a constant or may be specified according to inputted Mersenne primes p.sub.0, . . . , p.sub.N−1. When an assumed magnitude of the Mersenne primes p.sub.0, . . . , p.sub.N−1 is specified in advance, L can be a constant.

[0022] As illustrated in FIG. 2A, information identifying Mersenne primes p.sub.0, . . . , p.sub.N−1 is inputted to the inputting unit 13 first. An example of this information is the Mersenne primes p.sub.0, . . . , p.sub.N−1 themselves, n(0), . . . , n(N−1) or the like. The information identifying the Mersenne primes p.sub.0, . . . , p.sub.N−1, is sent to the mask generator 14 (step S13).

[0023] The mask generator 14 obtains and outputs a vector Mε{0,1}.sup.L (the second sequence), the vector M being constituted by L elements including values of digits of the Mersenne primes p.sub.0, . . . , p.sub.N−1 represented by binary numbers and a zero value (zero values). FIGS. 3A to 3C show specific examples of the vector M. The example of FIG. 3A is an example of n(0)= . . . =n(N−1)=7. In the vector M of this example, the top z elements (z=L−(n(0)+ . . . +n(N−1))) are 0, and all the remaining elements are 1. In other words, following the top subsequence zero constituted by z 0's, the Mersenne primes p.sub.N−1, . . . , p.sub.0 represented by binary numbers are arranged. The example of FIG. 3B is also an example of n(0)= . . . =n(N−1)=7. In this example, however, one Mersenne prime p.sub.i (i=N−1, . . . , 0) represented by a binary number is arranged following one element zero of 0, and 0's and Mersenne primes p.sub.i represented by binary numbers are alternately arranged. In FIG. 3C, following the top subsequence zero constituted by z 0's, the Mersenne primes p.sub.N−1, . . . , p.sub.0 represented by binary numbers are arranged. Here, all the Mersenne p.sub.N−1, . . . , p.sub.0 are not the same. Likewise, in the example of FIG. 3B, all the Mersenne p.sub.N−1, . . . , p.sub.0 may not be the same. The generated vector M is sent to the logical product arithmetic unit 16 (step S14).

[0024] The random number acquiring unit 15 determines whether a binary random number vector rε{0,1}.sup.L (the first sequence) remains in the storage 12, the binary random number vector r being an L-bit binary random number vector constituted by L elements (step S12). If the binary random number vector r remains, the random number acquiring unit 15 reads the binary random number vector r from the storage 12 and outputs it (step S15). The read binary random number vector r is deleted from the storage 12. On the other hand, if the binary random number vector r does not remain, the binary random number generator 11 generates an L-bit binary random number vector rε{0, 1}.sup.L and stores it into the storage 12, and the random number acquiring unit 15 reads the binary random number vector r from the storage 12 and outputs it (step S15). It is desirable that the binary random number generator 11 generates a plurality of binary random number vectors r by parallel processes and stores them into the storage 12 to speed up processing. The outputted binary random number vectors r are sent to the logical product arithmetic unit 16.

[0025] The logical product arithmetic unit 16 performs elementwise logical product operations (bit AND operations) between the binary random number vector r and the vector M to obtain and output a vector tε{0,1}.sup.L (the third sequence) which is a result of the operation. When the j-th element of the vector M (j=0, . . . , L−1) is 0, the j-th element of the vector t is 0. When the j-th element of the vector M is 1, the j-th element of the vector t is the j-th element of the binary random number vector r. That is, the vector t is a vector obtained by masking the binary random number vector r with the vector M. An element sequence (a subsequence) of the vector t corresponding to an element sequence of a Mersenne prime p.sub.i represented by a binary number, which is comprised in the vector M, is represented by a subsequence t.sub.i. For example, when the Mersenne prime p.sub.i represented by a binary number is an element sequence of the j.sub.1-th element to the j.sub.2-th element of the vector M, the subsequence t; is an element sequence of the j.sub.1-th element to the j.sub.2-th element of the vector t.sub.i For example, in the case of the example of FIG. 3A, the top z elements of the binary random number vector r is a subsequence r.sub.N constituted by (r.sub.N,z−1, . . . , r.sub.N,0)ε{0,1}.sup.z. However, since all the top z elements of the vector M are 0, all the top z elements of the vector t are also 0. Since all the subsequent elements of the vector M are 1, the subsequent subsequences t.sub.N−1, . . . , t.sub.0 (t.sub.i is a subsequence constituted by t.sub.i,6, . . . , t.sub.i,0ε {0,1}.sup.7) of the vector t are subsequences r.sub.N−1, . . . , r.sub.0 (r is a subsequence constituted by r.sub.i,6, . . . , r.sub.i,0ε{0,1}.sup.7) of the binary random number vector r. For example, in the case of the example of FIG. 3B, the binary random number vector r is constituted by subsequences r.sub.N−1, . . . , r.sub.0 (r.sub.i is a subsequence constituted by r.sub.i,7, . . . , r.sub.i,0ε{0,1}.sup.7). Since the vector M has N subsequences of 01111111 constituted by 0 and 1111111, the subsequences t.sub.N−1, . . . , t.sub.0 (t.sub.i is a subsequence constituted by t.sub.i,6, . . . , t.sub.i,0ε{0,1}.sup.7) of the vector t are the subsequences r.sub.N−1, . . . , r.sub.0 (r.sub.i is a subsequence constituted by r.sub.i,6, . . . , r.sub.i,0ε{0,1}.sup.7) of the binary random number vector r. For example, in the example of FIG. 3C, all the top z elements of the vector M are 0, and all the remaining elements are 1. Therefore, all the top z elements of the vector t are 0, and the subsequent subsequences t.sub.N−1, . . . , t.sub.0 are the subsequences r.sub.N−1, . . . , r.sub.0 of the binary random number vector r. The obtained vector t is sent to the outputting unit 18 (step S16).

[0026] The outputting unit 18 may output the vector t as it is or may output only the subsequences t.sub.N−1, . . . , t.sub.0 comprised in the vector t. Each subsequence t.sub.i (i=0, . . . , N−1) is treated as a random number on a residue field (a prime field) modulo the Mersenne prime p.sub.i (step S18). If a random number on the prime field is further required, the process from steps S13 to S18 or the process of S11 to S18 can be repeated.

Characteristics of the Present Embodiment

[0027] In the case of generating a random number on a prime field by a magnitude comparison between values represented by a binary random number vector r and a prime number p as done conventionally, if the number of elements of p represented by a binary number is small for the number of elements L of the binary random number vector r, the probability of random number generation on the prime field extremely decreases, and the random number generation speed decreases. For example, when the binary random number vector r indicates a uniform random number, and the number of elements of p represented by a binary number is L−1, the probability of random number generation on the prime field is 50% when p is a Mersenne prime and is below 50% when p is a prime number other than a Mersenne prime. This success probability decreases more when parallel processes are performed. For example, if it is attempted to generate 1000 prime numbers in parallel when the success probability is about 50%, the failure probability is about 99.9%, and the performance extremely decreases with only little success.

[0028] In comparison, since it is possible to certainly generate a random number on a prime field in the present embodiment, it is possible to generate a random number on a prime field at a high speed. Furthermore, the success probability does not decrease even if random number generation is performed by performing elementwise logical production operations (N≧2) simultaneously in parallel. Therefore, random numbers on prime fields can be generated at a higher speed by such parallel processes. Further, a lot of computers can perform bit AND operations (elementwise logical product operations) in parallel at a high speed and can efficiently implement the method of the present embodiment. Furthermore, the bit AND operation of the present embodiment can be executed by an L-bit register and can reduce the storage capacity in comparison with a method performing magnitude comparison such as a conventional one.

Second Embodiment

[0029] In the present embodiment, a uniform random number on a prime field is generated. Description will be made below mainly on points different from the matters described so far. As for the matters already described, the same reference numerals for the matters will be used, and description thereof will be omitted.

<Configuration>

[0030] As illustrated in FIG. 1, a random number generation apparatus 2 of the present embodiment has a binary random number generator 11, storage 12, an inputting unit 13, a mask generator 14, a random number acquiring unit 15, a logical product arithmetic unit 16, a determiner 27 and an outputting unit 18. The random number generation apparatus 2 may be configured, for example, by a predetermined program being read into the computer described above, or at least a part of components of the random number generation apparatus 2 may be configured only by hardware.

<Process>

[0031] The process of steps S11 to S16 is the same as that of the first embodiment. In the second embodiment, however, the Mersenne primes p.sub.i inputted to the inputting unit 13 and the vector t obtained at step S16 are inputted to the determiner 27. The determiner 27 determines whether any subsequence t.sub.i comprised in the vector t matches the Mersenne prime p.sub.i (i=0, . . . , N−1) (an equality determination) (step S27). If t.sub.i=p.sub.i is satisfied for any of i=0, . . . , N−1, the determiner 27 discards the vector t (t is rejected) and returns the process to step S12. On the other hand, t.sub.i≠p.sub.i is satisfied for all of i=0, . . . , N−1, the vector t is outputted to the outputting unit 18 (t is accepted). The subsequent process is the same as that of the first embodiment.

[0032] Though the determination of equality at step S27 may be performed independently for each i, batch processing may be performed as illustrated in FIG. 2B. In the example of FIG. 2B, a batch equality determiner of the determiner 27 simultaneously determines whether t.sub.i=p.sub.i is satisfied or not for all of i=0, . . . , N−1 (a batch determination of equality) to obtain a sequence of equality determination results x.sub.i. Here, x.sub.i=2.sup.k−1 is satisfied in the case of t.sub.i=p.sub.i, and x.sub.i=0 is satisfied in the case of t.sub.i≠p.sub.i; and k is a positive integer and satisfies 0<k×N≦L (step S271). Next, an aggregate arithmetic unit of the determiner 27 performs an aggregate OR operation (a sum operation) of the equality determination results x.sub.i (i=0, . . . , N−1) to obtain an aggregate determination result x which is a result of the operation. Here, when any equality determination result x.sub.i (i=0, . . . , N−1) is 2.sup.k−1 (when any equality determination result x.sub.i is not 0), x=2.sup.k−1 is satisfied; and, when all the equality determination results x.sub.i (i=0, . . . , N−1) are 0, x=0 is satisfied. Here, k′ is a positive integer and satisfies 0<k′≦L. Here, k=k′ may be satisfied, or k≠k′ may be satisfied (step S272). After that, the aggregate determiner of the determiner 27 determines whether x=−0 is satisfied or not (step S273). Here, if x=2.sup.k−1 is satisfied, the aggregate determiner discards the vector t (t is rejected) (step S274) and returns the process to step S12. On the other hand, if x=0 is satisfied, the aggregate determiner sends the vector t to the outputting unit 18 (t is accepted) (step S275).

[0033] In addition, the batch equality determiner may set x.sub.i=0 when t.sub.i=p.sub.i is satisfied and set x.sub.i=2.sup.k−1 when t.sub.i≠p.sub.i is satisfied, and the aggregate arithmetic unit may perform an aggregate AND operation (a product operation) of x.sub.i (i=0, . . . , N−1) to obtain an aggregate determination result x which is a result of the operation. Here, when any equality determination result x.sub.i (i=0, . . . , N−1) is 0, x=0 is satisfied; and, when all the equality determination results x.sub.i (i=0, . . . , N−1) are 2.sup.k−1, x=2.sup.k−1 is satisfied. In this case, if x=0 is satisfied, the aggregate determiner discards the vector t (t is rejected) and returns the process to step S12. On the other hand, if x=2.sup.k−1 is satisfied, the aggregate determiner sends the vector t to the outputting unit 18 (t is accepted).

Characteristics of the Present Embodiment

[0034] As described before, if the binary random number vector r indicates a uniform random number, each subsequence t.sub.i is a uniform random number on a residue field (a prime field) modulo the Mersenne prime p.sub.i. The probability of t.sub.i=p.sub.i being satisfied is about ½.sup.n(i)−1, and the probability of success is high irrespective of the magnitude of L. Since random number generation almost certainly succeeds in the present embodiment also, the success probability does not decrease almost at all even if the determination of equality for the subsequence t.sub.i (i=0, . . . , N−1) are simultaneously performed in parallel, and the probability of rejection at step S27 is low. For example, when p=2.sup.61−1 (that is, n(i)=61) is satisfied, the probability of failure in simultaneous generation in parallel of 1000 is ½.sup.51 which is sufficiently low, and overhead of redoing is extremely small. Therefore, by performing batch processing of the equality determination of step S27 as described above, it is possible to obtain a uniform random number on a prime field at a higher speed. That is, operation cost of the batch determination of equality and aggregate OR operation (or aggregate AND operation) described above is low. For example, in the case of L=256, a lot of computers can perform the processes in 1 clock. Further, a lot of current computers are provided with a branch prediction function and starts processing with a branch having more actual results, prior to performing branch calculation. Therefore, when the probability of redoing is low, the number of clocks required for conditional branch is substantially zero. Further, since the Mersenne primes p.sub.0, . . . , p.sub.N−1 comprised in the vector Mε{0,1}.sup.L, which is a mask, are identical with criteria for determination of equality, a register in which the vector M has been stored for a mask process can be used for the process of determination of equality also, and the processes can be realized with a small number of registers. Further, there is also an advantage that the determination of equality is more efficient in comparison with the magnitude comparison used in conventional systems (for the number of bits n, a circuit scale O(n)/depth O(n) or a circuit scale O(n log n)/depth O(log n) in the case of the magnitude comparison but a circuit scale O(n)/depth O(log n) in the case of the determination of equality).

Third Embodiment

[0035] In the present embodiment also, a uniform random number on a prime field is generated. Description will be made below mainly on points different from the matters described so far. As for the matters already described, the same reference numerals for the matters will be used, and description thereof will be omitted.

<Configuration>

[0036] As illustrated in FIG. 1, a random number generation apparatus 3 of the present embodiment has a binary random number generator 11, storage 12, an inputting unit 13, a mask generator 14, a random number acquiring unit 15, a logical product arithmetic unit 16, a determiner 37 and an outputting unit 18. The random number generation apparatus 3 may be configured, for example, by a predetermined program being read into the computer described above, or at least a part of components of the random number generation apparatus 3 may be configured only by hardware.

<Process>

[0037] The process of steps S11 to S16 is the same as that of the first embodiment. In the third embodiment, however, the vector t obtained at step S16 is inputted to the determiner 37. The determiner 37 determines whether any subsequence t.sub.i comprised in the vector t is a zero vector (t.sub.i=0) or not (step S37). If t.sub.i=0 is satisfied for any of i=0, . . . , N−1, the determiner 37 discards the vector t (t is rejected) and returns the process to step S12. On the other hand, t.sub.i≠0 is satisfied for all of i=0, . . . , N−1, the vector t is outputted to the outputting unit 18 (t is accepted). The subsequent process is the same as that of the first embodiment.

[0038] Similarly to the second embodiment, though the determination of equality at step S37 may be independently performed for each i, batch processing may be performed as illustrated in FIG. 2B. In the example of FIG. 2B, a batch equality determiner of the determiner 37 simultaneously determines whether t.sub.i=0 is satisfied or not for all of i=0, . . . , N−1 (a batch determination of equality) to obtain a sequence of equality determination results x.sub.i. Here, x.sub.i=2.sup.k−1 is satisfied in the case of t.sub.i=0, and x.sub.i=0 is satisfied in the case of t.sub.i≠0 (step S371). The subsequent steps S272 to S275 are the same as those of the second embodiment.

[0039] In addition, the batch equality determiner may set x.sub.i=0 when t.sub.i=0 is satisfied and set x.sub.i=2.sup.k−1 when t.sub.i≠0 is satisfied, and the aggregate arithmetic unit may perform an aggregate AND operation (a product operation) of x.sub.i (i=00, . . . , N−1) to obtain an aggregate determination result x which is a result of the operation. However, when any equality determination result x.sub.i (i=00, . . . , N−1) is 0, x=0 is satisfied; and, when all the equality determination results x.sub.i (i=0, . . . , N−1) are 2.sup.k−1, x=2.sup.k−1 is satisfied. In this case, if x=0 is satisfied, the aggregate determiner discards the vector t (t is rejected) and returns the process to step S12. On the other hand, if x=2.sup.k−1 is satisfied, the aggregate determiner sends the vector t to the outputting unit 18 (t is accepted).

Characteristics of the Present Embodiment

[0040] In the present embodiment also, it is possible to generate a uniform random number on a prime field at a high speed similarly to the second embodiment.

Other Modifications and the Like

[0041] The present invention is not limited to the embodiments described above. For example, the Mersenne primes p.sub.i may be set in a random number generation apparatus in advance. In this case, step S13 and the inputting unit 13 can be omitted. Furthermore, the vector M may be set in the random number generation apparatus in advance. In this case, step S14 and the mask generator 14 can be furthermore omitted. Further, the binary random number vector r may be stored in the storage 12 in advance. Further, Mersenne numbers which are composite numbers may be used instead of Mersenne primes. For example, all of the Mersenne numbers p.sub.0, . . . , p.sub.N−1 may be composite numbers or the Mersenne numbers p.sub.0, . . . , p.sub.N−1 may comprise prime numbers and composite numbers.

[0042] The various processes described above are not only executed in order of the description. They may be executed in parallel or individually according to processing capacity of an apparatus to execute the processes or as necessary. In addition, it goes without saying that the various processes can be appropriately changed within a range not departing from the spirit of the present invention.

[0043] In the case of realizing the configuration described above by a computer, processing content of a function which each apparatus should have is written in a program. By executing the program on the computer, the processing functions described above are realized on the computer. The program in which the processing content is written can be recorded in a computer-readable recording medium. An example of the computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory and the like.

[0044] Distribution of this program is performed, for example, by sales, transfer, lending and the like of a portable recording medium such as a DVD and a CD-ROM in which the program is recorded. Furthermore, a configuration is also possible in which the program is stored in a storage device of a server computer to distribute the program by transferring the program from the server computer to other computers via a network.

[0045] For example, a computer which executes such a program stores the program recorded in the portable recording medium or transferred from the server computer into its storage device once. At the time of executing a process, the computer reads the program stored in its recording device and executes a process in accordance with the read program. As another form of executing this program, it is also possible for the computer to read the program directly from the portable recording medium and execute the process in accordance with the program, and, furthermore, it is also possible for the computer to, each time a program is transferred to the computer from the server computer, execute a process in accordance with the received program in order. A configuration is also possible in which the program is not transferred from the server computer to the computer is not performed, but the processes described above are executed by a so-called ASP (Application Service Provider) type service for realizing a processing function only by an instruction to execute the program and acquisition of a result.

[0046] Although the processing functions of the present apparatus are realized by causing a predetermined program to be executed on a computer in the above embodiment, at least a part of the processing functions may be realized by hardware.

INDUSTRIAL APPLICABILITY

[0047] The present invention can be used for various cryptography techniques, for example, secret sharing, secret calculation, public key cryptography, symmetric key cryptography, digital signature and the like.

DESCRIPTION OF REFERENCE NUMERALS

[0048] 1-3: random number generation apparatus