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.
@article{bwmeta1.element.doi-10_1515_forma-2015-0029,
author = {Hiroyuki Okazaki},
title = {Algebra of Polynomially Bounded Sequences and Negligible Functions},
journal = {Formalized Mathematics},
volume = {23},
year = {2015},
pages = {371-378},
zbl = {1334.94090},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_forma-2015-0029}
}
Hiroyuki Okazaki. Algebra of Polynomially Bounded Sequences and Negligible Functions. Formalized Mathematics, Tome 23 (2015) pp. 371-378. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_forma-2015-0029/
[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41–46, 1990. | Zbl 06213858
[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] | Zbl 1321.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.