Math and stuff

Notes for the post by Ethereum. Prerequisites First and foremost, one should understand RLP encoding before jumping into MPT for a reason you might not expect. This is not because one might want to encode the MPT. This is because a MPT is an RLP-encodable object. More specifically, an RLP-encodable...

Summary of the post by Ethereum An item is defined to be: a byte array, or a list of items. How to encode a byte array An array containing a single byte in the range of [0x00, 0x7f] is its own encoding. 0x11 is 0x11. Note that 0x11 is technically...

Exercise 1.34(a) and 1.35 in An Introduction to Mathematical Cryptography. These exercises are based on a special case of Hensel’s Lemma. Let $p$ be an odd prime and an integer $1 \leq b \leq p - 1$ be given. Let $S_e = \{ 1 \leq x \leq p^e - 1...

This is my notes for Theorem 2.32 in An Introduction to Mathematical Cryptography. Let $G$ be a finite abelian group and $g \in G$ be an element of order $N = q_1^{e_1} \cdots q_t^{e_t}$. We will solve $h = g^x$. First, let $g_i = g^{N / q_i^{e_i}}$ and $h_i =...

This is my notes for Section 3.6 in An Introduction to Mathematical Cryptography. Underlying idea Let $N \in \mathbb{N}$ be a large, composite number. We can tell that it is not prime from a probabilistic primality test such as Miller-Rabin. We would like to find a prime factor efficiently. As...