Math and stuff

We prove Exercise 3.31 from P.184 of An Introduction to Mathematical Cryptography. (a) Let $\epsilon = 1/20$. \[\begin{align*} (\ln X)^{\epsilon} < \ln (L(X)) < (\ln X)^{1 - \epsilon} &\iff (\ln X)^{2\epsilon - 1} < \ln (\ln(X)) < (\ln X)^{1 - 2\epsilon} \\ &\iff (\ln X)^{-9/10} < \ln (\ln(X)) < (\ln...

Let $L(X) = e^{\sqrt{(\ln X)(\ln \ln X)}}$. We claim that $L(X)$ is subexponential. \[\begin{align*} e^{\sqrt{(\ln X)(\ln \ln X)}} &> e^{\sqrt{(\ln \ln X)(\ln \ln X)}} \\ &= e^{\ln \ln X} \\ &= \ln X. \end{align*}\] \[\begin{align*} e^{\sqrt{(\ln X)(\ln \ln X)}} &< e^{\sqrt{(ln X)(\ln X)}} \\ &= e^{\ln X} \\ &= X....

Suppose that $p, q_1, q_2$ are prime numbers such that $p - 1 = q_1 q_2$ with $q_1 \ne q_2$. Suppose that we can solve $g^x = h$ in $O(S_{q})$ if $\abs{g} = q$ for any $g, e \in \mathbb{F}_p$. Note that an element in $\mathbb{F}_p$ has an order of...

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there? We need to solve the following system of equations: \[\begin{align*} x &\equiv...

Let $\mathbb{F}$ be a finite field. We consider the sequence $0, 1, 1 + 1, 1 + 1 + 1, \cdots$ in $\mathbb{F}$. Since $\mathbb{F}$ is finite, we eventually have duplicates. Furthermore, the duplicate must happen in the first $\abs{\mathbb{F}} + 1$ terms. There are two possibilities: $0 = 1...