Fast Fourier transform
In this article we will discuss an algorithm that allows us to multiply two polynomials of length $n$ in $O(n \log n)$ time, which is […]
Month: July 2021
Arbitrary-Precision Arithmetic
Arbitrary-Precision arithmetic, also known as “bignum” or simply “long arithmetic” is a set of data structures and algorithms which allows to process much greater numbers […]
Submask Enumeration
1. Enumerating all submasks of a given mask Given a bitmask $m$, you want to efficiently iterate through all of its submasks, that is, masks […]
Balanced Ternary
1. Overview This is a non-standard but still positional numeral system. Its feature is that digits can have one of the values -1, 0 and […]
Montgomery Multiplication
Many algorithms in number theory, like prime testing or integer factorization, and in cryptography, like RSA, require lots of operations modulo a large number. A multiplications like $x […]
Discrete Root
The problem of finding a discrete root is defined as follows. Given a prime $n$ and two integers $a$ and $k$, find all $x$ for […]
Primitive Root
1. Definition In modular arithmetic, a number $g$ is called a primitive root modulo n if every number coprime to $n$ is congruent to a […]
Discrete Logarithm
The discrete logarithm is an integer $x$ satisfying the equation $$a^x \equiv b \pmod m$$ for given integers $a$, $b$ and $m$. The discrete logarithm […]
Factorial modulo $p$
In some cases it is necessary to consider complex formulas modulo some prime $p$, containing factorials in both numerator and denominator, like such that you […]
Chinese Remainder Theorem
The Chinese Remainder Theorem (which will be referred to as CRT in the rest of this article) was discovered by Chinese mathematician Sun Zi. 1. […]
Linear Congruence Equation
This equation is of the form: $$a \cdot x = b \pmod n,$$ where $a$, $b$ and $n$ are given integers and $x$ is an […]
Modular Multiplicative Inverse
1. Definition A modular multiplicative inverse of an integer $a$ is an integer $x$ such that $a \cdot x$ is congruent to $1$ modular some modulus $m$. […]
Number of divisors / sum of divisors
In this article we discuss how to compute the number of divisors $d(n)$ and the sum of divisors $\sigma(n)$ of a given number $n$. 1. […]
Euler’s totient function
Euler’s totient function, also known as phi-function $\phi (n)$, counts the number of integers between 1 and $n$ inclusive, which are coprime to $n$. Two numbers are […]
Integer factorization
In this article we list several algorithms for factorizing integers, each of them can be both fast and also slow (some slower than others) depending […]
Primality tests
This article describes multiple algorithms to determine if a number is prime or not. 1. Trial division By definition a prime number doesn’t have any […]
Sieve of Eratosthenes Having Linear Time Complexity
Given a number $n$, find all prime numbers in a segment $[2;n]$. The standard way of solving a task is to use the sieve of Eratosthenes. […]
Sieve of Eratosthenes
Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment $[1;n]$ using $O(n \log \log n)$ operations. The algorithm is […]
Fibonacci Numbers
The Fibonacci sequence is defined as follows: $$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$ The first elements of the sequence (OEIS […]
