Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-20
2003-12-23
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06668265
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus and method for outputting a sequence of vectors, a data recording medium, and a carrier wave signal.
More particularly, the present invention relates to an apparatus and method for outputting a sequence of higher dimensional random vectors whose limiting distribution is expressed by an analytical density function, after associating two vector sequence generating methods by which sequences of random vectors whose limiting distribution is expressed by a known analytical density function are output, and a data recording medium storing a program which realize the above vector sequence output.
2. Description of the Related Art
Many random number generating methods utilizing recurrence formulas have been known conventionally. Many fields require random number generation. Monte-Carlo method for simulation in physics and engineering fields utilizes the random numbers.
CDMA (Code Division Multiple Access) technology for mobile phone communication assigns PN (Pseudo Noise) code to each user in order to share the limited band among many users. The PN code is generated based on the random numbers.
Moreover, public key encryption employed in telecommunication technologies utilizes the random numbers for generating public keys. Demands for such the encryption has been developing because stronger protection has been required as telecommunications such as internet has been widely used.
Traditional methods for generating the random numbers usually utilize recurrence formulas. Especially, multiplication recurrence formulas have been used widely for many years. However, such the multiplication recurrence formula also has raised problems regarding to finite periodicity. Recently, rational maps have been applied to the recurrence formulas to generate random numbers as chaos theory has been developing. The rational map is a result of the addition theorem of an elliptic function (including a trigonometric function). Demands for the random number generation by such the method which utilizes the rational map have been developing, because such the method has the following advantages.
(1) Non-cyclical random number sequence generation by which the numbers are proven to be chaotic (thus, aperiodic):
(2) Sequences of rational numbers result from rational number seeds (initial values given to the recurrence formula); and
(3) Known analytic function acts as the density function expressing random number distribution.
Known rational maps which bring the above advantages are: an Ulam-von Neumann map (equation 1), a cubic map (equation 2), a quintic map (equation 3), and the like.
f
(
x
)
=
4
x
(
1
-
x
)
EQUATION
1
f
(
x
)
=
x
(
3
-
4
x
)
2
EQUATION
2
f
(
x
)
=
x
(
5
-
20
x
+
16
x
2
)
2
EQUATION
3
Regardless of the different rational maps above, the equation 4 represents a density function expressing distribution of a random number sequence x[i] which results from the following recurrence formula (where 0<&xgr;<1; &xgr; is an arbitrary initial value).
x
[
0
]=&xgr;
x[i+
1
]=f
(
x[i
]) (
i
≧0)
ρ
(
x
)
=
1
π
x
(
1
-
x
)
EQUATION
4
A rational map with a parameter, such as a Katsura-Fukuda map, a generalized Ulam-von Neumann map (equation 5), a generalized cubic map, a generalized Chebyshev map, or the like may be applied to the recurrence formula.
f
(
l
,
m
,
x
)
=
4
x
(
1
-
x
)
(
1
-
lx
)
(
1
-
mx
)
1
-
Ax
2
+
Bx
2
+
Cx
4
where
A
=
2
(
l
+
m
+
l
m
)
B
=
8
l
m
C
=
l
2
+
m
2
-
2
l
m
-
2
l
2
m
-
2
l
m
2
+
l
2
m
2
EQUATION
5
For example, if the random number sequence result from the above recurrence formula employing the generalized Ulam-von Neumann map (equation 5), limiting distribution of the resultant random number sequences is expressed by the following density function (equation 6) which includes the parameter of the generalized Ulam-von Neumann map.
1
K
(
l
,
m
)
x
(
1
-
x
)
(
1
-
lx
)
(
1
-
mx
)
where
K
(
l
,
m
)
=
∫
0
1
ⅆ
u
(
1
-
u
2
)
(
1
-
lu
2
)
(
1
-
mu
2
)
EQUATION
6
The Katsura-Fukuda map is the same as the generalized Ulam-von Neumann map (equation 5) where m=0.
Unexamined Japanese Patent Application KOKAI No. H10-283344 by the inventor of the present invention discloses a technique for generating random numbers with utilizing rational maps. Theoretical backgrounds for the technique are disclosed in the following documents.
S. M. Ulam and J. von Neumann, Bull. Math. Soc. 53 (1947) pp. 1120.
R. L. Adler and T. J. Rivlin, Proc. Am. Math. Soc. 15 (1964) pp. 794.
K. Umeno, Method of constructing exactly solvable chaos, Phys. Rev.E (1997) Vol. 55 pp. 5280-5284.
Conventionally, a random number sequence (a sequence of random one-dimensional vectors) result from the above random number generating method by applying a sequence of scalars (one-dimensional vectors) to the recurrence formula as the seed.
However, such the conventional methods have the following problems.
For carrying out the Monte-Carlo method in dimension at least two, a sequence of random vectors of dimensions at least two is required. However, the conventional random number generating method generates a sequence of random numbers corresponding to a sequence of scalars (one-dimensional vectors). When the Monte-Carlo method is applied to simulation in three-dimensional space, three-value selection from head of the sequence may be required for necessary times. However, such operation causes deviation of random number distribution, thus, error convergence will be poor.
Moreover, the public key encryption requires paired integers as the random number. However, the conventional method can not perform simultaneous generation of the integers to be paired. This will make a security hole, thus, the encryption may be cracked.
Under such the circumstances, there is a great demand for an apparatus and method for outputting a sequence of vectors each of which comprises plural pairs of random numbers each being generated simultaneously as a multi-dimensional random vector, and for expressing distribution of the output vector sequence by an analytic density function.
SUMMARY OF THE INVENTION
The present invention has been made for overcome the above problems. It is an object of the present invention to provide to an apparatus and a method for outputting a sequence of higher dimensional random vectors by associating two vector sequence generating methods by which sequences of random vectors whose distribution is expressed by a known analytic density function are output, and distribution of the resultant sequence of random vectors is expressed by an analytic density function, and to provide a data recording medium storing a program which realizes the above.
To accomplish the above object, the following invention will be disclosed in accordance with the principle of the present invention.
As shown in
FIG. 1
, an apparatus
100
for outputting a sequence of vectors according to a first aspect of the present invention comprises a first storage
101
, a first calculator
102
, a second storage
103
, a second calculator
104
, an output
105
, a first update
106
, and a second update
107
.
(a) the first storage
101
stores vector x of dimension at least 1;
(b) the first calculator
102
calculates vector x′=f(x) which utilizes a first rational vector map f to which the vector x stored in the first storage
101
is input;
(c) the second storage
102
stores vector y of dimension at least 1;
(d) the second calculator
104
calculates vector y′=g(x, y
Communications Research Laboratory, Ministry of Posts and Teleco
Do Chat C
Luce Forward Hamilton & Scripps LLP
Ngo Chuong Dinh
LandOfFree
Apparatus and method for outputting sequence of vectors,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for outputting sequence of vectors,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for outputting sequence of vectors,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3164412