# Algebra of Polynomially Bounded Sequences and Negligible Functions

Formalized Mathematics (2015)

- Volume: 23, Issue: 4, page 371-378
- ISSN: 1426-2630

## Access Full Article

top## Abstract

top## How to cite

topHiroyuki Okazaki. "Algebra of Polynomially Bounded Sequences and Negligible Functions." Formalized Mathematics 23.4 (2015): 371-378. <http://eudml.org/doc/276933>.

@article{HiroyukiOkazaki2015,

abstract = {In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability of succeeding any attacks against the cryptosystem is negligible. First, we formalize the algebra of polynomially bounded sequences [20]. Next, we formalize negligible functions and prove the set of negligible functions is a subset of the algebra of polynomially bounded sequences. Moreover, we then introduce equivalence relation between polynomially bounded sequences, using negligible functions.},

author = {Hiroyuki Okazaki},

journal = {Formalized Mathematics},

keywords = {polynomially bounded function; negligible functions},

language = {eng},

number = {4},

pages = {371-378},

title = {Algebra of Polynomially Bounded Sequences and Negligible Functions},

url = {http://eudml.org/doc/276933},

volume = {23},

year = {2015},

}

TY - JOUR

AU - Hiroyuki Okazaki

TI - Algebra of Polynomially Bounded Sequences and Negligible Functions

JO - Formalized Mathematics

PY - 2015

VL - 23

IS - 4

SP - 371

EP - 378

AB - In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability of succeeding any attacks against the cryptosystem is negligible. First, we formalize the algebra of polynomially bounded sequences [20]. Next, we formalize negligible functions and prove the set of negligible functions is a subset of the algebra of polynomially bounded sequences. Moreover, we then introduce equivalence relation between polynomially bounded sequences, using negligible functions.

LA - eng

KW - polynomially bounded function; negligible functions

UR - http://eudml.org/doc/276933

ER -

## References

top- [1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41–46, 1990. Zbl06213858
- [2] Mihir Bellare. A note on negligible functions, 2002.
- [3] Józef Białas. Group and field definitions. Formalized Mathematics, 1(3):433–439, 1990.
- [4] Czesław Byliński. The complex numbers. Formalized Mathematics, 1(3):507–513, 1990.
- [5] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1): 55–65, 1990.
- [6] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153–164, 1990.
- [7] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357–367, 1990.
- [8] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47–53, 1990.
- [9] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165–167, 1990.
- [10] Oded Goldreich. Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, 2001.
- [11] Krzysztof Hryniewiecki. Basic properties of real numbers. Formalized Mathematics, 1(1): 35–40, 1990.
- [12] Andrzej Kondracki. Basic properties of rational numbers. Formalized Mathematics, 1(5): 841–845, 1990.
- [13] Artur Korniłowicz. On the real valued functions. Formalized Mathematics, 13(1):181–187, 2005.
- [14] Jarosław Kotowicz. Real sequences and basic operations on them. Formalized Mathematics, 1(2):269–272, 1990.
- [15] Jarosław Kotowicz. Convergent sequences and the limit of sequences. Formalized Mathematics, 1(2):273–275, 1990.
- [16] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part I: Theory. Formalized Mathematics, 9(1):135–142, 2001.
- [17] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part II: Examples and problems. Formalized Mathematics, 9(1):143–154, 2001.
- [18] Eugeniusz Kusak, Wojciech Leończuk, and Michał Muzalewski. Abelian groups, fields and vector spaces. Formalized Mathematics, 1(2):335–342, 1990.
- [19] Adam Naumowicz. Conjugate sequences, bounded complex sequences and convergent complex sequences. Formalized Mathematics, 6(2):265–268, 1997.
- [20] Hiroyuki Okazaki and Yuichi Futa. Polynomially bounded sequences and polynomial sequences. Formalized Mathematics, 23(3):205–213, 2015. doi:10.1515/forma-2015-0017.[Crossref] Zbl1321.68276
- [21] Henryk Oryszczyszyn and Krzysztof Prażmowski. Real functions spaces. Formalized Mathematics, 1(3):555–561, 1990.
- [22] Konrad Raczkowski and Andrzej Nędzusiak. Real exponents and logarithms. Formalized Mathematics, 2(2):213–216, 1991.
- [23] Konrad Raczkowski and Andrzej Nędzusiak. Series. Formalized Mathematics, 2(4):449–452, 1991.
- [24] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1 (2):329–334, 1990.
- [25] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501–505, 1990.
- [26] Wojciech A. Trybulec. Groups. Formalized Mathematics, 1(5):821–827, 1990.
- [27] Wojciech A. Trybulec. Vectors in real linear space. Formalized Mathematics, 1(2):291–296, 1990.
- [28] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67–71, 1990.
- [29] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825–829, 2001.
- [30] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73–83, 1990.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.