Views and branches


Branches of abstract algebra

High level




Mathematics Subject Classification

Problem hardness and complexity

P, NP, NP-complete, NP-hard

A language L is in NP if for every word x in the language there exists a witness w which is of length polynomial in the length of x and given the witness and the word you can verify language-membership in polynomial time.

Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.

P for Polynomial time

NP for Non-deterministic Polynomial time

Computational complexity

Time complexity

To express the running time of an algorithm one can use a combination of two ideas. Suppose an algorithm, running on an input of size n takes 6n2+100n+300 machine instructions. This expression is a polynomial with n as variable (indeterminate). The 6n2 squared term becomes larger than the remaining terms, 100n+300 once n becomes large enough, 20 in this case. The running time of this algorithm is specified as n2 dropping the coefficient 6 and the remaining terms 100n+300.

The less significant terms and the constant coefficients are dropped to focus on the important part of an algorithm's running time—its rate of growth—without getting mired in details. This is called 'asymptotic notation', of which there are the following forms.

Circuit complexity

Famous solved problems



Soundness and completeness

In mathematical logic, logical systems are sound if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system. The converse of soundness is known as completeness. A formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; otherwise the system is said to be incomplete.

Interactive Proofs

In 'A paradoxial solution to the signature problem' Goldwasser, Micali and Rivest specify that the standard definition of interactive proofs require

Probabilistically Checkable Proofs (PCP)

Used a.o. in SNARKS.



Arithmetic is the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th century, Italian mathematician Giuseppe Peano formalized arithmetic with his Peano axioms, which are important to the field of mathematical logic today.

Modular arithmetic

p-adic numbers


Algebra is the study of variables and the rules for manipulating these variables in formulas; it is a unifying thread of almost all of mathematics. Many areas of mathematics belong to algebra, some having "algebra" in their name, such as commutative algebra, and some not, such as Galois theory.

Algebra began with computations similar to those of arithmetic, with letters standing for numbers. This allowed proofs of properties that are true no matter which numbers are involved. For example, in the quadratic equation ax^{2}+bx+c=0, where a, b, c can be any numbers whatsoever (except that a cannot be 0 and the quadratic formula can be used to quickly and easily find the values of the unknown quantity x which satisfy the equation. That is to say, to find all the solutions of the equation.

Abstract algebra

Sets and cosets




Basics Roots

Quadratic residues, Legendre and Jacobi symbols


Finding a square root of a number modulo a large composite n is equivalent to factoring (which is widely believed to be a hard problem), hence has been used for constructing cryptographic schemes such as the Rabin cryptosystem and the oblivious transfer.

The quadratic residuosity problem is the basis for the Goldwasser-Micali cryptosystem.

Legendre - prime p and integer a

Jacobi - [composite] integer n and integer a


In algebra a polynomial is an expression of the form a0+a1x+...+anxn. The ai are called coefficients (typically real or complex numbers). The x is a variable, substituting an arbitrary number for it a well defined number is obtained.

A polynomial of ring R is a polynomial where the coefficients are element of R, and x is a symbol not belonging to R, called the indeterminate over R.

Addition and product for polynomials over R is defined, and the set of polynomials over R forms a ring, called the polynomial ring over R, R[x]. The highest exponent of n is called the degree of the polynomial.

The prime elements of the ring F[x] are called irreducible polynomials. Polynomials of postive degree can be uniquely factorised. An element of a field F is called a root of the polynomial if its value is zero.

In number theory, there's Lagrange's theorem, about how frequently a polynomial over the integers may evaluate to a multiple of a fixed prime.

Elliptic curve

embedding degree k is ... singular hyperelliptic

Ways of specifying ECs:

EC pairings

Refer also to pairing-based crypto.

NIST: a pairing is a function that maps a pair of points on an elliptic curve into a finite field. Their unique properties have enabled many new cryptographic protocols that had not previously been feasible.

The Weil pairing was first introduced into cryptography by Menezes, Okamoto and Vanstone (A. J. Menezes, T. Okamoto and S. A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inf. Theory, 39, No. 5 (1993) 1639{1646) to attack the ECDLP on certain elliptic curves.

The Tate pairing was introduced to cryptography by Frey and Rueck (G. Frey and H.-G. Rueck, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp., 62, No.206 (1994) 865{874}) in their extension of the work of Menezes, Okamoto and Vanstone.

Can be calculated with the Miller algorithm.



Intro and overview

Set theory and Z


The formal specification notation Z is based on Zermelo-Fraenkel set theory and first order predicate logic. It has been developed by the Programming Research Group at the Oxford University Computing Laboratory and elsewhere since the late 1970s, inspired by Jean-Raymond Abrial's seminal work. Z is now defined by the ISO/IEC 13568 standard and is public domain.

Z tools




Alloy = logic + language + analysis, where Focused on software engineering

Proof assistants

Isabelle (Cambridge/Muenchen)


Coq is a formal proof management system. It provides a formal language to write mathematical definitions, executable algorithms and theorems together with an environment for semi-interactive development of machine-checked proofs. Typical applications include the certification of properties of programming languages (e.g. the CompCert compiler certification project, the Verified Software Toolchain for verification of C programs, or the Iris framework for concurrent separation logic), the formalization of mathematics (e.g. the full formalization of the Feit-Thompson theorem, or homotopy type theory), and teaching.

Process calculus

Finite State Machines

Proposition logic, SAT, SMT

In mathematical logic, satisfiability and validity are elementary concepts of semantics.


SAT refers to the propositional (or boolean) satisfiability problem.


Satisfiability Modulo Theories (SMT) is an area of automated deduction that studies methods for checking the satisfiability of first-order formulas with respect to some logical theory T of interest. It differs from general automated deduction in that the background theory T need not be finitely or even first-order axiomatizable, and specialized inference methods are used for each theory.

FOL and predicate logic




Subjective logic

Deontic logic


Number theory




Graph in ZK


DSP - FFT - wavelets - compression


Information and computation

Linear Programming




Refer also to LTK and LTK-SageMath.



Mathworld - Matworks - Matlab



When a statistician passes the airport security check, they discover a bomb in his bag. He explains. "Statistics shows that the probability of a bomb being on an airplane is 1/1000. However, the chance that there are two bombs at one plane is 1/1000000. So, I am much safer..."

The same statistician later drowned in a river with an average depth of 30 cm.