The Montgomery reduction algorithm finds the remainder of a division. Many cryptographic schemes work with numbers modulo a prime. When you have to multiply two numbers with e.g. 128 bits each, first you multiply them the usual way (there are many techniques for this) to obtain a 256-bit (“double precision”) number. Then you need to [...]
The Euclidian algorithm finds the greatest common divisor of two numbers a and b. There is an extended version of it that also finds two numbers x and y such that ax + by = gcd(x,y). This is useful when searching for modular multiplicative inverses. The algorithm is simple, but I’ve never bothered to study [...]
The Frobenius endomorphism is defined as: where p is the characteristic of the ring you’re working with. Simple, right? If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back [...]
When working with finite fields, if the number of elements is a prime power with m > 1, you can represent the elements as polynomials with degree m-1 and do the field addition and multiplication modulo a irreducible polynomial with degree m. The field GF(5) is composed by the numbers 0 to 4. We don’t [...]