I need to write a proof for neglible functions in cryptography, i have this definition:
Let negl1 andnegl2 be negligible functions. Then:
1. The function negl3 defined by negl3(n) =negl1(n)+negl2(n) is negligible.
2. For any positive polynomial p, the function negl4 defined by negl4 (n) =p(n)·negl1(n) is negligible.
Now, I need to prove the second part of this definition, relying on this definition:
A function f from the natural numbers to the non-negative real numbers is negligible if for
every positive polynomial p there is an N such that for all integersn > N it holds that f(n) < 1 / p(n).
So I thought I would start with the following:
negl_4(n) = p(n) * negl_1(1)
= p_i(n) * 1/p_j(n)
where the two p's are two differnt polynomials. Is there some way that I could convert the last statement here to 1 / p(n), with some new polynomial function?
To show $\textrm{negl}_4$ is negligible:
Let $q(n)$ be any arbitrary polynomial in $n$.
Apply the definition of negligibility of $\textrm{negl}_1$ to the new polynomial $p(n)\cdot q(n)$. We conclude there is some $N$ such that for all $n >N$ we have
$$\textrm{negl}_1(n) < \frac{1}{p(n)q(n)} \implies \textrm{negl}_4(n)= p(n) \cdot \textrm{negl}_1(n) < p(n) \cdot \frac{1}{p(n)q(n)} = \frac{1}{q(n)}$$
And as $q(n)$ was arbitrary, we are done.