JP2001109375A - Pseudo random number generator - Google Patents

Abstract

PROBLEM TO BE SOLVED: To generate pseudo random numbers at a high speed by decreasing a memory capacity and moreover reducing computational complexity when generating random numbers with a high probability to be prime numbers from plural random numbers, as pseudo random numbers. SOLUTION: Plural random numbers are generated according to a control signal SET and a clock signal, and an initial value is generated based on these random numbers. The plural random numbers are given to counters 3011-301m, and the counters are controlled according to the control signal. Selectors 3021-302m select any of input values based on the outputs of the counters. The outputs of the selectors are added to storage values by an adder 303 into a total value. A register 304 stores either the initial value or the total value as a storage value of the above and output it as a random number.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for generating a pseudo-random number having a high probability, which is a prime number.

[0002]

2. Description of the Related Art In general, when generating prime numbers, since there is no formula for generating prime numbers, integers are randomly generated, and it is determined whether or not these integers are prime numbers.
It is necessary to repeat such an operation until a prime number is obtained. However, when determining whether or not an integer is a prime number, a large amount of computation is required.In practice, instead of simply generating an integer at random, an “integer with a high probability of being a prime number” is used. Is generated, and it is determined whether or not the generated integer is a prime number determination.

Here, a method of generating “an integer having a high probability of being a prime number” will be outlined with reference to FIG. First, an integer X is randomly generated (procedure 610). That is, a random number is generated. If the integer X is even, it is obviously not a prime number, so the least significant bit of the integer X is set to 1 (procedure 620).

[0004] Next, as j = 1 (Step 630), X is examined whether divisible by _{P j} (Step 640).
Then, in step 640, if divisible, in step 61
Return to 0. In step 640, if not divisible, j =
m (m is a positive integer) (step 65)
0). If j = m, the process ends and X is output as a pseudo-random number. On the other hand, if j = m is not satisfied, j = j + 1 (procedure 660) and the procedure returns to procedure 640. Here,
_{P 1, P 2, ...,} P m are different small primes from each other.

[0005] If the pseudo-random number X is generated using the method shown in FIG. 6, X does not have P ₁ , P ₂ ,..., P _m as prime factors, and is simply an integer generated at random. The probability of being a prime number is higher.

[0006]

According to the prime number theorem,
It is known that the probability that an n-bit (n is a positive integer) randomly generated integer is a prime number is about 1 / n. Therefore, in the method described with reference to FIG. 6, it is necessary to randomly generate about n integers until one n-bit prime is obtained.

For this reason, in public key cryptography in which a prime number of hundreds to thousands of bits is used as a secret key, 1
There is a problem that hundreds to thousands of integers are generated uselessly until one prime number is obtained, and a large amount of calculations must be performed.

As a technique for reducing the amount of calculation when generating prime numbers, a technique using the Chinese remainder theorem is known. Briefly describing this method, for any given non-negative integer A, α _j = {A mod (P _j −1)}
When you +1, because it is always _{α j ≠ 0 (modP j)} , P 1, P 2, ..., if the _{P m} is a prime number, simultaneous linear congruence _{X = α j (mod P j} ), X = α ₂ (mod P ₂ ),
, X = α _m (mod P _m ) exists. The solution is X
(Note that it is represented by the same X), X is not divisible by any of P ₁ , P ₂ ,..., P _m .

[0009] _{P 1,} P _{2, ...,} a _{P m,} if from the smaller of two or more of prime numbers and the side-by-side series in the order, a small prime number _P 1 of X are _m, P _{2, ...,} prime the _{P m} Therefore, the probability that X is a prime number is higher than the probability that a randomly given integer is a prime number.

Note that the solution X of the above-mentioned simultaneous linear congruential equation is X
= Α₁(P₁P₂… P_m/ P₁) Β ₁+ Α₂(P₁P₂
… P_m/ P₂) Β₂+ ... + α_m(P₁P₂… P_m/
P_m) Β _m(Mod P₁P₂… P_mEasily asked by
Is known to be. Where β_j(J = 1, 2,
…, M) is the congruential formula (P₁P₂… P_m/ P_j) Β_j= 1
(Mod P_j). Because of this,
Instead of outputting the number A as it is, the operation described above
Output X obtained from A as a random number
For example, a random number having a high probability of being a prime number can be obtained.

However, the random number generation method based on the Chinese remainder theorem has a problem that high-speed processing cannot be performed because multiplication and division are required. Of course, if multiplication / division is replaced with addition / subtraction using an operation table, high-speed processing can be performed. However, a large-capacity memory for storing the operation table is required.

The conventional prime number generation method and public key cryptography are described in, for example, “Applied Cryptography (2nd Edition)” by Schneier (Bruce Schneier, Applied
Cryptography: Protocols, Algorithms, and Source C
ode in C, Second Edition, John Wiley & Sons, Inc. 19
96) has a detailed explanation. For a method of generating random numbers using the Chinese remainder theorem, see Japanese Patent Application No. 9-2903.
No. 50 has a detailed explanation. Therefore, here
Detailed description is omitted.

An object of the present invention is to provide a method and an apparatus which can generate a pseudo random number at a high speed with a small amount of calculation.

Another object of the present invention is to provide an apparatus which has a small memory capacity and can generate pseudo random numbers at high speed.

[0015]

According to the present invention, there is provided an apparatus used for generating a random number having a high probability of being a prime number from a plurality of random numbers as a pseudo-random number, comprising: an inverted signal obtained by logically inverting a control signal; When a clock pulse obtained by a logical sum with a clock signal is applied and the control signal is "1", each time the clock signal is input, the first to mth clock signals are input.
(M is an integer of 2 or more) random number generation device, and a first to obtain a first to m-th addition result by adding "1" to each of the first to m-th random numbers An adder for multiplying the first to m-th addition results by first to m-th predetermined multiplication numbers to generate first to m-th multiplication results, respectively; Second adding means for adding the m-th multiplication result to obtain the addition result and outputting the addition result as the initial value; and when the clock signal is input when the control signal is "1". The first to m-th random numbers are set as first to m-th initial state values, respectively, and when the control signal is "0" and the carry is "1", the clock signal is input. Every time the count value is increased by "1" and the count value is set to a predetermined count value. There and as a carry output "1"
And the first through m-th counters outputting "0" as a carry output when the count value is other than the predetermined count value, and "1" as a carry input of the first counter. Supply means for giving the carry output of the first through (m-1) th counters to the carry input of the second through mth counters;
And the first through m-th multiples of the first through m-th selection values, respectively, are given, and the carry input of the j-th (j is any number from 1 to m) counter is input. If it is "0", it selects "0" and outputs it as a selected value. If the carry input of the j-th counter is "1" and its carry output is "0", the j-th selected value is Second selector means for outputting as the selected value and outputting a j-th multiple as the selected value when the carry input of the j-th counter is "1" and the carry output is "1"; Third addition means for adding a storage value and the selected value to output a total value, and storing the initial value as the storage value when the clock signal is supplied when the control signal is "1". When the control signal is "0", the total value is calculated each time the clock signal is supplied. Pseudorandom number generator, wherein the stored value every time the clock signal is supplied as well as stores the serial memory value having a register means for outputting as said pseudo-random number is obtained.

Further, according to the present invention, there is provided an apparatus used for generating a random number having a high probability of being a prime number from a plurality of random numbers as a pseudo-random number, wherein a control signal is logically inverted and an inverted signal and a clock signal are generated. When a clock pulse obtained by a logical sum is applied and the control signal is “1”, the first to m-th (m is 2) every time the clock signal is input.
A random number generation device that generates a random number of the above (integer), a first adding unit that adds “1” to each of the first to m-th random numbers to obtain first to m-th addition results, Multiplying means for multiplying the first to m-th addition results by first to m-th predetermined multiplication numbers to generate first to m-th multiplication results, respectively; A second adding means for adding the multiplication result and outputting the addition result, and subtracting a first to m-th subtraction number from the addition result to obtain a first
First subtraction means for obtaining a subtraction result from the first to the m-th subtraction number; first comparison means for comparing the addition result with the first to the m-th subtraction number to output a comparison result; First selector means for selectively outputting the addition result and the first and m-th subtraction results as the initial value in response to the control signal, and the clock signal is input when the control signal is "1". Then, the first to m-th random numbers are set as first to m-th initial state values, respectively, and when the control signal is "0" and the carry is "1", the clock signal is input. Each time the count value is incremented by "1", if the count value is a predetermined count value, "1" is output as a carry output, and the count value is other than the predetermined count value. Output "0" as carry output The first to m-th counters, and giving "1" to the carry input of the first counter to the first to (m-1) th carry to the carry input of the second to m-th counters. And a supply means for providing a carry output of the counter, and the first to m-th selected values and the first to m-th multiples of twice the first to m-th selected values, respectively, and j-th (j If the carry input of the counter of any of 1 to m) is "0", "0" is selected and output as a selected value, and the carry input of the j-th counter is "1" and If the carry output is "0", the j-th selected value is output as the selected value, and the carry input of the j-th counter is "1" and the carry output is "1".
, A second selector for outputting a j-th multiple as the selected value, a third adding unit for adding a stored value and the selected value to output a total value, and Second subtraction means for subtracting the first to m-th subtraction numbers to obtain first to m-th subtraction calculation results, and comparing the total value with the first to m-th subtraction numbers, respectively. Second comparison means for outputting a comparison calculation result according to the comparison result, and second selector means for selectively outputting the sum value and the first and m-th subtraction calculation results as select values according to the comparison calculation result. When the control signal is "1", the initial value is stored as the storage value when the clock signal is supplied, and when the control signal is "0", the select value is stored each time the clock signal is supplied. Is stored as the storage value The pseudorandom number generator is obtained, characterized in that the stored value each time the clock signal is applied and a register means for outputting as said pseudo-random numbers.

[0017]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to the drawings.

Referring to FIG. 1, the pseudo random number generation device shown includes a random number generation device 110, an initial value generation device 120, and a prime candidate generation device 130. Input terminal 162
Is inverted by the NOT circuit 150 to form an inverted control signal. The OR circuit 140 calculates the OR of the clock signal CLK supplied from the input terminal 161 and the inversion control signal, and supplies the OR signal to the clock input terminal of the random number generation device 110.

Each time a clock pulse (OR signal) is supplied to the clock input terminal, the random number generator 110 generates a new random number (AI _m ,..., AI ₂ , AI ₁ ).
Here, AI _j is an integer satisfying 0 ≦ AI _j <P _j −1. Note that P ₁ , P ₂ ,..., P _m are predetermined prime numbers of 2 or more, and are different from each other.

When the control signal SET supplied from the input terminal 162 is “1”, the random number generation device 110
Each time a clock pulse is supplied from 61, a new random number (AI _m ,..., AI ₂ , AI ₁ ) is generated.

The initial value generation device 120 includes the random number generation device 1
From the random number sequence (AI _m ,..., AI ₂ , AI ₁ ) from 10, a value XI used as an initial value of the prime candidate generation device 130 described later is generated, and the initial value data is output.

The prime candidate generating device 130 is connected to the input terminal 14
When the clock signal is supplied from the input terminal 161 when the control signal SET supplied from the second random number 2 is “1”, the random number sequence (AI _m ,..., AI ₂ ,.
AI ₁ ) and the initial value X output from the initial value generation device 120
I is set as an initial state. Further, the prime candidate generation device 130 outputs the control signal S supplied from the input terminal 162.
When ET is 0, a new random number (integer) is output via the output terminal 161 each time a clock pulse is supplied from the input terminal 161.

Here, the configuration of the initial value generating device will be described with reference to FIG. The random numbers AI _j output from the random number generation device 110 (see FIG. 1) are
_j (j = 1 to m), and each of the adders 201
_j . The adder 201 _j has an input terminal 211 _j
"1" is added to the integer supplied from, and the obtained addition result is output. The multiplier 202 _j multiplies the output of the adder 201 _j by δ _j and outputs a multiplication result. Where δ
_j is a predetermined integer defined as δ _j = P ₁ P ₂ ... P _m / P _j .

The adder 203 includes multipliers 202 _{1 to} 202
The outputs of _m are added, and the addition result is output from the output terminal 212.

Next, the configuration of the prime candidate generation device will be described with reference to FIG. P _j −1 base counter 301 _j
When the control signal SET "1" supplied from the input terminal 312, from the input terminal 315 when the clock pulse is supplied, the value supplied from the input terminal 311 _j (random number generator 110 shown in FIG. 1 The output random number AI _j ) is set as an initial value.

When the control signal SET supplied from the input terminal 312 is “0” and the carry input is “1”, the P _j −1-ary counter 301 _j outputs the input terminal 315 Increments the counter value by “1” every time a clock pulse is supplied from the counter (where the counter value is P _j
If it is equal to -1, the counter value is returned to "0").

If the counter value is equal to P _j -1 then:
The P _j −1 base counter 301 _j outputs “1” as a carry output, and otherwise outputs “0” as a carry output. And P ₁ -ary counter 3
“1” is supplied to the carry input of 01 ₁ and P _j −
The carry input of the binary counter 301 _j includes P _j−1 −
The carry output of the _primary counter 301 _j-1 is supplied (here, j = 2, 3,..., M).

The selector 302 _j has a counter 301 _j
Carry inputs and carry outputs are, are supplied as a control signal, carry input of counter 301 _j is "0"
If so, "0" is selected and output. Also, carry output of the counter 301 _j with carry input of counter 301 _j is "1" if "0", and selects and outputs the [delta] _j. Then, carry input of the counter 301 _j is "1"
If the carry output of the counter 301 _j is “1”,
And selects and outputs the 2δ _j.

The adder 303 has a register 304 to be described later.
Is stored in the selector 302 ₁~ 302_mOutput
And outputs the addition result. Register 304 is
The control signal SET supplied from the input terminal 312 is “1”
, A clock pulse is supplied from the input terminal 315
Then, the value supplied from the input terminal 313 (the initial value shown in FIG.
X output from the output terminal 212 by the period value generation device 120
I) is stored.

Further, the register 304 is connected to the input terminal 31.
When the control signal SET supplied from 2 is “0”, each time a clock pulse is supplied from the input terminal 315, the output of the adder 303 is stored. The value stored in the register 304 is supplied to the adder 303 and output from the output terminal 314 as a random number (integer).

Here, the operation of the pseudorandom number generator according to the present invention will be described with reference to FIGS.

According to the Chinese remainder theorem, P ₁ , P ₂ ,
.., _Pm is a prime number, for α _j such that 0 <α _j <P _j , the simultaneous linear congruential equation X about X = α ₁ (mo
d P ₁ ), X = α ₂ (mod P ₂ ),..., X = α _m (mod
There is a solution of P _m ), and the solution X is (note that it is represented by the same X), and X = α ₁ (P ₁ P ₂ ... P _m / P ₁ ) β ₁
+ Α ₂ (P ₁ P ₂ ... P _m / P ₂ ) β ₂ +... + Α _m (P ₁
It is given by _{P 2 ... P m / P m} ) β m + γP 1 P 2 ... P m. Here, β _j (j = 1, 2,..., M) is an integer satisfying the congruence formula (P ₁ P ₂ ... P _m / P _j ) β _j = 1 (mod P _j ), and γ is an arbitrary It is an integer.

X generated in this manner is represented by P ₁ , P
_2, ..., since not divisible either P _m, than an integer randomly generated, there is a high probability a prime number. This principle is the principle used when generating a prime number candidate in the specification of Japanese Patent Application No. 9-290350.

The pseudo-random number generator shown in the figure generates a prime candidate more efficiently by using the following three principles in addition to this principle.

First, according to the first principle, the calculation efficiency is improved by the difference. That is, corresponding to (α ₁ , α ₂ ,..., Α _m ), the simultaneous linear congruential equation X about X = α ₁ (mod P
₁ ), X = α ₂ (mod P ₂ ),..., X = α _m (mod
P _m ) is X ₀ , while (α ₁ , α ₂ ,..., Α
_{j + 1} ,..., α _m ), a simultaneous linear congruential equation for X, X = α ₁ (mod P ₁ ), X = α ₂ (mod P ₂ ),.
X = α _{j + 1} (mod P _j ),..., X = α _m (mod P _m )
If the solution is _{X j,} using the Chinese remainder theorem, direct _{(α 1, α 2, ...} , α j + 1, ..., α m) from without seeking _{X j, X j = X 0} + δ _j (where δ _j = (P ₁
X _j can be obtained by the operation of P ₂ ... P _m / P _j ) (a constant defined by β _j ), that is, by one addition.

In the method of generating prime candidates described in the specification of Japanese Patent Application No. 9-290350, multiplication and division are required. In order to eliminate the multiplication and division and generate prime candidates only by addition and subtraction, , It is necessary to replace multiplication and division with addition and subtraction using an operation table.

According to the second principle, (α₁, Α₂,…,
α_m) And how to change the difference
Consecutive primes without the appearance of one prime candidate
Number candidates can be generated. That is, α_j= A_j+1
And A_jIs 0 ≦ A_j<P_j-1 but (A_m,…,
A₂, A₁) Is the Pth digit_jExpressed as a decimal number
As a number, and A_jIs the jth digit from the bottom of the number
The number (A_m, ..., A₂, A₁) By 1
Go to (However, if overflow occurs, return to 0
), The same number (A_m, ..., A₂, A₁), Immediately
And the same (α₁, Α₂,…, Α_m) Pairs appear
And not. Of course, the number (A_m, ..., A₂, A₁) To P
₁P₂… P_mWhen the number is increased, the same number (A_m,…,
A₂, A₁) Appears, but usually P₁P₂… P_mIs
Chosen for very large values (hundreds to thousands of bits)
So, in effect, the same number (A_m, ..., A₂, A₁) Comes out
It will not manifest. And P₁, P₂, ..., P_mNo
A value that is not divisible by the deviation is set as the initial value of X, and A
_jIs P_jWhen less than -2, A_jWhen 1 is added to
If X is δ_jIs added. On the other hand, A_jIs P_j-2
When equal, A_jIs added to 1 and A_jReturns to “0”
If X is 2δ_j(A_jIs P_j-1
When viewed as a remainder system, the value changes only by "1".
Not, but the corresponding α _jChanges the value by “2”
2δ_jMust be added).

[0038] In this way, if Yuke to update the value of X, the value of X is, _{always, P 1, P 2, ...} , not divisible by any of the _{P m.} Further, the same value of X does not appear repeatedly. In the above-described manner, when a carry occurs, a plurality of additions (at most m times) are performed at once, but on average, one addition is still performed for one operation. This is done only to the extent that this does not sacrifice computational efficiency.

The third principle is based on the Chinese remainder theorem.
In the prime candidate generation method, β_jIs a joint expression (P₁P₂
… P_m/ P_j) Β_j= 1 (mod P_j)
Not a number, but β_jIs P_jIf the integer is relatively prime to
Prime number candidates can be generated. That is, the congruential expression (P₁P₂… P
_m/ P_j) Β_j= 1 (mod P_jAn integer β that satisfies
_jInstead of β '_jIs used, X = α₁(P₁P₂
… P_m/ P₁) Β '₁+ Α₂(P₁P₂… P_m/ P₂)
β '₂+ ... + α_m(P₁P₂… P_m/ P_m) Β '_m+ Γ
P₁P₂… P_mThe value of X given by
Simultaneous primary joint expression X = α₁(Mod P₁), X = α₂(Mo
d P₂), ..., X = α_m(Mod P_mIs not a solution of)
But β '_jIs P_jIs relatively prime with α_jβ '_j/ Β
_j≠ 0 (mod P_j), The value of X is related to X
Simultaneous primary congruence formula X = α₁β ' ₁/ Β₁(Mod
P₁), X = α₂β '₂/ Β₂(Mod P₂), ..., X =
α_mβ ' _m/ Β_m(Mod P_m) And still
And P₁, P₂, ..., P_mIt is not divisible by either.

For this reason, by selecting β _j to be “1”, a slight but constant δ _j = (P ₁ P ₂ ... P _m / P
_j ) The number of digits of β _j can be shortened to save memory required for storing constants.

Accordingly, in the pseudo random number generation device, first, the control signal SET supplied to the input terminal 162 is set to “1”, one clock pulse is supplied to the input terminal 161, and then the control signal supplied to the input terminal 162 is supplied. The signal SET is set to “0”. Thereafter, the degree to supply the clock pulses to the input terminal _{161, P 1, P 2,} ..., the value of X can not be divided either _{P m} is obtained at the output terminal 163. Although It is noted that in FIG. 1 to FIG. 3, the initial value of Aj is expressed as AI _j, the initial value of X are expressed as XI, _also, the _P j -1 binary counter 301 _j The content corresponds to _Aj .

Next, with reference to FIG.
20 will be described.

In the example shown in FIG. 2, while the output of the adder 203 is supplied to the output terminal 212 as it is,
In the example shown in FIG. 4, the output of the adder 203 is the subtractor 40
1, the comparator 402, and the selector 403, and the output of the selector 403 is supplied to the output terminal 212.

The subtractor 401 outputs the output of the adder 203 (Z
), Respectively, 1P ₁ P ₂ ... P _m , 2P ₁ P ₂
... _{P m,} ..., by subtracting the mP _{1 P} 2 ... Pm, resulting _{Z-1P 1 P 2 ... P} m, Z-2P 1 P 2 ... P m, ..., Z
-MP ₁ P ₂ ... the _{P m} outputs respectively.

The comparator 402 outputs Z and _1P 1 _P 2 _{... P m} of the adders _{203, 2P 1 P 2 ... P} m, ..., m
P ₁ P ₂ ... by comparing the magnitude of the _{P m} and outputs a comparison result. The selector 403, the output of comparator 402 (the comparison result) indicates that it is a _{Z <P 1 P 2 ... P} m,
The output of the adder 203 is selected and output. On the other hand, the output of the comparator 402 is kP ₁ P ₂ ... P _m ≦ Z <(k + 1) P ₁
If it indicates that a _{P 2} ... P _m, and selects and outputs the output _{Z-kP 1 P 2 ... P} m of the subtracter 401.

Thus, the output of selector 403 is always
A smaller value than the _{P 1} P ₂ ... P _m. Note that the range of the output of the selector 403 can be changed by changing the selection rule in the selector 403 as necessary.

Referring to FIG. 5, prime candidate generating apparatus 130
Another example will be described.

In the example shown in FIG. 3, while the output of the adder 303 is supplied to the register 304 as it is,
In the example shown in FIG. 4, the output of the adder 303 is
1, the comparator 502 and the selector 503,
The output of the selector 503 is supplied to the register 304.

The subtractor 501 calculates 1P ₁ P ₂ ... P _m , 2P ₁ P ₂ from the output (Z) of the adder 303.
... _{P m,} ..., by subtracting the mP _{1 P} 2 ... _{P m,} resulting _{Z-1P 1 P 2 ... P} m, Z-2P 1 P 2 ... P m, ..., Z
-MP ₁ P ₂ ... the _{P m} outputs respectively.

The comparator 502 outputs Z and _1P 1 _P 2 _{... P m} of the adders _{303, 2P 1 P 2 ... P} m, ..., m
Comparing the magnitude of the _{P 1} P ₂ ... P _m, and outputs a comparison result. The selector 503, the output of comparator 502 (the comparison result) of the show that is _{Z <P 1 P 2 ... P} m, and selects the output of the adder 303. On the other hand, the comparator 5
02 is kP ₁ P ₂ ... P _m ≦ Z <(k + 1) P ₁ P
₂ ... If it indicates that a _{P m,} and selects and outputs the output _{Z-kP 1 P 2 ... P} m of the subtracter 501.

Thus, the output of the selector 503 is always
A smaller value than the _{P 1} P ₂ ... P _m. Note that the range of the output of the selector 503 can be changed by changing the selection rule in the selector 503 as necessary.

In the above description, the adder 203 and the adder 203
Although an adder with m inputs is used as the adder 303,
Using a two-input adder instead of a power adder,
The addition may be performed. When adding in time division
Is the constant δ₁, Δ₂,…, Δ _mIs located at the lower digit of
Only the ones (ie those with small subscripts)
Remember, other constants are generated by calculation when needed
You may. That way, the methods needed to remember the constants are
The amount of moly can be saved.

[0053]

As described above, according to the present invention, a prime number candidate can be generated by only one addition (even when adding by time division, it can be generated by about one addition on average). ), There is an effect that a prime candidate, that is, a random number having a high probability of being a prime number can be generated at high speed.

Further, in the present invention, the number m of random numbers generated
Even if is increased, the amount of calculation required to generate prime candidates hardly changes, and as a result, there is an effect that the probability that a prime candidate is a prime number can be increased without increasing the amount of calculation.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an example of a pseudo random number generation device according to the present invention.

FIG. 2 is a block diagram showing an example of an initial value generation device shown in FIG.

FIG. 3 is a block diagram illustrating an example of a prime candidate generation apparatus illustrated in FIG. 1;

FIG. 4 is a block diagram showing another example of the initial value generation device shown in FIG. 1;

FIG. 5 is a block diagram showing another example of the prime candidate generation device shown in FIG. 1;

FIG. 6 is a flowchart for explaining a conventional pseudo random number generation technique.

[Explanation of symbols]

 110 random number generator 120 initial value generator 130 prime candidate generator

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Hiroharu Yoshikawa 3-12-1, Kachidoki, Chuo-ku, Tokyo Inside Ricoh System Development Co., Ltd. (72) Inventor Liang, 3-12-1, Kachidoki, Chuo-ku, Tokyo F-term (reference) in Ricoh System Development Co., Ltd. 5J104 AA23 GA04 NA04

Claims (6)

[Claims] 1. A device used for generating a random number having a high probability of being a prime number from a plurality of random numbers as a pseudo-random number, wherein a control signal is obtained by a logical sum of a logically inverted inverted signal and a clock signal. A random number generation device that generates a first to m-th (m is an integer of 2 or more) random numbers each time the clock signal is input when a clock pulse is supplied and the control signal is “1”; A first adding means for adding “1” to each of the m-th random numbers to obtain first to m-th addition results; and a first to m-th random number added to the first to m-th addition results, respectively. Multiplying means for multiplying a predetermined multiplication number to generate first to m-th multiplication results; adding the first to m-th multiplication results to obtain an addition result; A second adding means for outputting the value as a value, and the control signal When the clock signal is inputted when the control signal is "1", the first to m-th random numbers are respectively set as first to m-th initial state values, and when the control signal is "0", carry is carried out. Is "1", the count value is incremented by "1" each time the clock signal is input, and if the count value is a predetermined count value, "1" is output as a carry output, and If the value is other than the predetermined count value, the first to m-th counters output "0" as a carry output, and "1" is supplied to the carry input of the first counter to provide the second counter. Supply means for providing the carry output of the first to (m-1) th counters to the carry input of the mth counter; the first to mth selected values and the first to mth counters 1 to m-th, each of which is twice the selected value of When a multiple is given and the carry input of the j-th (j is any number from 1 to m) counter is “0”, “0” is selected and output as a selected value, and the j-th counter digit is output. If the carry input is "1" and the carry output is "0", the j-th selected value is output as the selected value, and the carry input of the j-th counter is "1" and the carry output. Is the first value, the second selector means for outputting the j-th multiple as the selected value, the third adding means for adding the stored value and the selected value to output the total value, When the clock signal is supplied when the signal is "1", the initial value is stored as the storage value. When the control signal is "0", the total value is stored each time the clock signal is supplied. And the clock signal is given. Pseudorandom number generator, characterized in that it comprises a register means for outputting the stored value as the pseudo-random number. 2. A device used for generating a random number having a high probability of being a prime number from a plurality of random numbers as a pseudo-random number, wherein a control signal is obtained by a logical sum of a logically inverted inverted signal and a clock signal. A random number generation device that generates a first to m-th (m is an integer of 2 or more) random numbers each time the clock signal is input when a clock pulse is supplied and the control signal is “1”; A first adding means for adding “1” to each of the m-th random numbers to obtain first to m-th addition results; and a first to m-th random number added to the first to m-th addition results, respectively. Multiplying means for multiplying a predetermined multiplication number to generate first to m-th multiplication results, and second adding means for adding the first to m-th multiplication results and outputting an addition result , From the result of the addition
First subtraction means for subtracting the first through m-th subtraction numbers to obtain first through m-th subtraction results; and comparing the addition result with the first through the m-th subtraction numbers to obtain a comparison result. First comparing means for outputting, the first selector means for selectively outputting, as the initial value, the addition result and the first and m-th subtraction results according to the comparison result; When the clock signal is inputted when the control signal is "1", the first to m-th random numbers are respectively set as first to m-th initial state values, and when the control signal is "0", carry is carried out. Is "1", the count value is incremented by "1" each time the clock signal is input, and if the count value is a predetermined count value, "1" is output as a carry output, and The value is other than the predetermined count value First to m-th counters that output “0” as carry output; and “1” to the carry input of the first counter, and the first to m-th counters provide the carry input of the second to m-th counters. 1 to the (m-1) th
And a supply means for providing a carry output of the counter, and the first to m-th selected values and the first to m-th multiples of twice the first to m-th selected values, respectively, and j-th (j Is 1
If the carry input of any of the counters is any of "0", "0" is selected and output as a selected value, and the carry input of the j-th counter is "1" and its digit If the carry output is "0", the j-th selected value is output as the selected value. If the carry input of the j-th counter is "1" and the carry output is "1", the j-th selected value is output. Second selector means for outputting a multiple as the selected value, third adding means for adding the stored value and the selected value to output a total value, and the first to m-th values respectively based on the total value. A second subtraction means for subtracting the subtraction number from the first to obtain first to m-th subtraction calculation results, and comparing the total value with the first to the m-th subtraction numbers to output a comparison calculation result A second comparing means, and the total value and the first and the second values in accordance with a result of the comparison calculation. Second selector means for selectively outputting the m-th subtraction calculation result as a select value, and storing the initial value as the storage value when the clock signal is supplied when the control signal is "1". Register means for storing the select value as the storage value each time the clock signal is applied when the control signal is "0", and outputting the storage value as the pseudo-random number each time the clock signal is applied; A pseudorandom number generation device, comprising: 3. The pseudo-random number generator according to claim 1, wherein when the j-th random number is represented by AI _j , AI
_j is an integer satisfying 0 ≦ AI _j <P _j −1;
A pseudorandom number generator, wherein _j is a prime number of 2 or more. 4. The pseudo-random number generator according to claim 3, wherein when the j-th predetermined multiplier and the j-th selected value are represented by δ _j , δ _j is δ _j = P ₁ P ₂ ...
Pseudorandom number generator which is a integer defined by P m _/ P _j. 5. The pseudo-random number generation device according to claim 4, wherein the predetermined count value is P _j −1. 6. The pseudorandom number generator according to claim 2.
, The j-th random number is AI_jWhen represented by AI_jIs
0 ≦ AI_j<P_jIs an integer satisfying −1, and P_jIs 2
The prime number, j-th predetermined multiplier and
The j-th selected value is δ_jWhen represented by the above δ_jIs δ_j= P
₁P₂… P_m/ P_jIs an integer defined by
The determined count value is P_j-1;
The first to m-th subtraction numbers are each 1P₁P₂… P_m, 2
P₁P₂… P_m, ..., mP₁P ₂… P_mAnd the ratio
If the comparison result is the addition result <P₁P₂… P_mAnd the second
1 selector means sets the addition result as the initial value.
And the comparison result is jP₁P₂… P_m≤ addition result
<(J + 1) P₁P₂… P_m, The j-th subtraction result
Is selected as the initial value, and the comparison calculation result
Is the addition calculation result <P₁P₂… P_m, The second
Selector means for converting the addition calculation result into the select value
And the comparison calculation result is jP₁P₂… P_m
≦ addition calculation result <(j + 1) P₁P₂… P_mIs
The j-th subtraction calculation result is selected as the select value.
A pseudo-random number generator, characterized in that: