MATHEMATICS
- High level overviews
- Associations
- Universities
- Notation and terminology
- Problem hardness and complexity
- Famous solved problems
- Proofs
- Arithmetic
- Calculus - differential, integral, ...
- Linear algebra - concerns linear equations and linear maps, and their representations (vector/matrix)
- Abstract algebra - generalisation of arithmetic, using set, group, ring, field, polynomial, elliptic curve, pairing, ...
- Logic
- Finite State Machines
- Proposition logic - SMT, SAT
- FOL
- Subjective logic
- Deontic logic
- Number theory
- Graphs
- Transformations
- Information and computation
- Tools
- Humour
Views and branches
Views
- Arithmetic (Egypt - numbers), geometry (Greece - shape), calculus (Europe - 17th century - motion, change, space).
- Counting (arithmetic - number theory - primes), reasoning and communication (logic, Venn diagrams, set theory, grammar), motion and change (series, functions, calculus, differentials, integration, analytic number theory), shape (geometry), symmetry (symmetry groups, sphere packing), position (topology, surfaces, knots, elliptic curves)
- mathematica (...)
Branches of abstract algebra
- Abstract algebra (how to specify sets, groups, rings, fields, how to compute with their elements)
- Abstract Algebra - great overview + Sage exercises, covering:
- The Integers
- Groups
- Cyclic Groups
- Permutation Groups
- Cosets and Lagrange’s Theorem
- Introduction to Cryptography
- Algebraic Coding Theory
- Isomorphisms
- Normal Subgroups and Factor Groups
- Homomorphisms
- Matrix Groups and Symmetry
- The Structure of Groups
- Group Actions
- The Sylow Theorems
- Rings
- Polynomials
- Integral Domains
- Lattices and Boolean Algebras
- Vector Spaces
- Fields
- Finite Fields
- Galois Theory
High level
Overview
Associations
Universities
Mathematics Subject Classification
Notation
General
When g is a generator of a group G, < g > refers to the subgroup generated by g.
When specifying a security parameters such as k, it is customary that 1k refers to a bitstring of lenght k (and not to the exponent).
A map is often specified by an 'accent circonflexe', the 'little roof': ê.
A random selection is sometimes indicated by the use of the dollarsign, $.
Exponentiation:
- The square root √ may be specified as an inverse exponent, i.e. x1/2, the nth root as x1/n.
- Negative exponent: n-1 = 1/n
- Strong DH: given a sequence g, gx, gx2, ..., gxq for a group G of prime order p, output a pair (c, g(x+c)-1) with c in Zp. Written otherwise, g(x+c)-1 = g1/(x+c) = the (x+c)th root of g. Where you can select c but don't know x.
Affine:
- Affine - Wikipedia
- Affine Coordinate System, a coordinate system that can be viewed as a Cartesian coordinate system where the axes have been placed so that they are not necessarily orthogonal to each other. See Tensor - Wikipedia.
- A tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other tensors. There are many types of tensors, including scalars and vectors (which are the simplest tensors), dual vectors, multilinear maps between vector spaces, and even some operations such as the dot product. Tensors are defined independent of any basis, although they are often referred to by their components in a basis related to a particular coordinate system; those components form an array, which can be thought of as a high-dimensional matrix.
- Affine combination - Wikipedia
- An affine combination of x1, ..., xn is a linear combination a1x1 + a2x2 + ... + anxn. Here, x1, ..., xn can be elements (vectors) of a vector space over a field K, and the coefficients ai are elements of K.
- The elements x1, ..., xn can also be points of a Euclidean space, and, more generally, of an affine space over a field K. In this case the ai are elements of K (or R for a Euclidean space), and the affine combination is also a point.
- Affine transformations - Wikipedia
- Affine transformations - brilliant.org
- An affine transformation is a type of geometric transformation which preserves collinearity (if a collection of points sits on a line before the transformation, they all sit on a line afterwards) and the ratios of distances between points on a line. Types of affine transformations include translation (moving a figure), scaling (increasing or decreasing the size of a figure), and rotation (turning a figure about a point).
- Note that affine transformations can be done Rn, for n GE 1, although some of the transformations do not make sense for n=1. Matrix algebra will be used to unify the presentation. To get an unique affine transformation matrix, one more point is needed than the n of the Rn space. It also is assumed that the points do not share a common Rn−1 space. For example, in R2 space, 3 points are required and they must not all in in the same R1 space, that is, must not be collinear.
Integers
The word integer comes from the Latin integer meaning "whole" or (literally) "untouched", from in ("not") plus tangere ("to touch"). The use of the letter Z to denote the set of integers comes from the German word Zahlen ("numbers") and has been attributed to David Hilbert.
The symbol Z is often annotated to denote various sets, with varying usage amongst different authors: Z+, Z+ or Z> for the positive integers.
Some authors use Z* for non-zero integers, while others use it for non-negative integers, or for {–1, 1} (the group of units of Z.
Additionally, Zp is used to denote either the set of integers modulo p (i.e., the set of congruence classes of integers), or the set of p-adic integers.
Nigel Smart
Book 'Cryptography Made Simple':
- Z/NZ = {0, ..., N-1}, Z/NZ is the set of remainders modulo N
- An alternative notation for Z/NZ is ZN
- The set of intervertable elements in Z/NZ are (Z/NZ)* = { x ∈ Z/NZ: gcd(x,N)=1}
- In case N is a prime p we have (Z/pZ)* = {1, ..., p-1}
- Fp = Z/pZ = {0, ..., p-1}, which is a finite field of characteristic p - alternative notation: Zp
- Fp* = (Z/pZ)* = {1, ..., p-1}
Fields and cardinality
Identification and authentication
Cryptographers often refer to the demonstration of identity as identification. The reason is the paper 'How to prove yourself: Practical solutions to identification and signature problems' by Fiat and Shamir in Andrew M. Odlyzko, editor, Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986.
Computer scientists prefer to call this authentication. In the field of biometric recognition, identification is the 1:n match for subjects that are not collaborative.
Preneel suggests to always specify whether you mean entity or data authentication.
Problem hardness and complexity
P, NP, NP-complete, NP-hard
- P versus NP - Wikipedia
- The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
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
- Polynomial time - Wikipedia
- An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k.
- Problems for which a deterministic polynomial-time algorithm exists belong to the complexity class P.
- Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".
NP for Non-deterministic Polynomial time
- Non-deterministic Polynomial time - Wikipedia
- Have proofs verifiable in polynomial time.
- It is easy to see that the complexity class P (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem.
- A ZKP is constructed on top of an NP problem. In ZKP, a prover intends to prove to a verifier that he knows the solution (witness) of some published NP-problem, without revealing this solution.
- Illustrations of NP problems include
- 'The Boolean circuit foo is satisfiable by some input qux.' - Given qux, you could plug it in the circuit and determine if foo is satisfied or not in poly-time. But finding such a qux which satisfies foo will be difficult.
- NP-completeness - short for "nondeterministic polynomial-time complete - Wikipedia
- Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly.
- The SAT problem is the first problem that was proven to be NP-complete; see Cook–Levin theorem.
- This means that all problems in the complexity class NP are at most as difficult to solve as SAT. There is no known algorithm that efficiently solves each SAT problem, and it is generally believed that no such algorithm exists; yet this belief has not been proved mathematically, and resolving the question of whether SAT has a polynomial-time algorithm is equivalent to the P versus NP problem, which is a famous open problem in the theory of computing.
- List of NP complete problems - Wikipedia
- Karp's list of NP complete problems - Wikipedia
- NP-hardness - short for "nondeterministic polynomial-time complete - Wikipedia
- is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP".
- A simple example of an NP-hard problem is the subset sum problem.
- Subset Sum Problem - Wikipedia
- There is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T.
- The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete.
IP - Interactive Proof = PSPACE
The class IP (interactive polynomial time) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE.
The result was established in a series of papers
- Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs
- Shamir established that IP=PSPACE - where PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
The concept of an interactive proof system (IPS) was introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An IPS consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct.
The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in Bounded-error Probabilistic Polynomial time (BPP) is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)
Bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.
Computational complexity
Time complexity (i.e. running time)
- Time complexity - Wikipedia
- Describes the amount of computer time it takes to run an algorithm.
- Commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
- Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
- Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size.
To express the running time of an algorithm one can use a combination of two ideas.
- One needs to determine how long the algorithm takes, in terms of the size of its input.
- Also, one needs to consider how fast a function grows with the input size, the rate of growth of the running time.
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.
- Asymptotic notation - Khan Academy
- big-Θ (big-theta) notation expresses that a running time, once n gets large enough, the running time is at least k1⋅n and at most k2⋅n for some constants k1 and k2.
- big-Ω (big-omega) notation expresses that an algorithm takes at least a certain amount of time, without providing an upper bound.
- Big-Ω notation is used for asymptotic lower bounds, it bounds the growth of the running time from below for large enough input sizes.
- big-O notation, typically O(n), O(log n), O(n^a), etc., where n is the size in units of bits needed to represent the input.
- Algorithmic complexities can be classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity O(n) is a linear time algorithm and an algorithm with time complexity O(n^a) for some constant a > 1 is a polynomial time algorithm.
- Big O notation - Wikipedia
The complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2nO(1).
Circuit complexity
- Circuit complexity - Wikipedia
- branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them.
- A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits
Lattices complexity
Learning With Errors complexity
Based on the idea of representing secret information as a set of equations with errors. LWE is a way to hide the value of a secret by introducing noise to it. It refers to the computational problem of inferring a linear n-ary function f over a finite ring from given samples yi = f(xi) some of which may be erroneous.
Famous solved problems
Proofs
Basics
- Proof - an overloaded term - Wikipedia
- Propositional proof - 'truth' - Wikipedia
- Formal proof - Wikipedia - a finite sequence of sentences (called well-formed formulas in the case of a formal language), each of which is an axiom, an assumption, or follows from the preceding sentences in the sequence by a rule of inference.
- Proof complexity - Wikipedia - concerned with proving proof-length lower and upper bounds in various propositional proof systems - connects to SAT solvers
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
- that the verifier accepts a correct proof, and
- rejects an incorrect assertion with a probability of at least 2/3.
- ... however, one usually tries to obtain a probability less than 2-k where k is the security parameter...
- ...a way to achieve this 'security amplification' is to take a protocol with 1/3 error probability, run it O(k) times and accept/reject by majority vote
An interactive proof system (IPS) is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not.
The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has 'convinced' itself that it is correct.
Classes of interactive proofs are:
- NP
- Arthur-Merlin and Merlin-Arthur protocols
- Public coin protocol versus private coin protocols
- IP
- QIP - for quantum interactive proof system, and the corresponding complexity class QIP. A series of results culminated in a 2010 breakthrough that QIP = PSPACE
- ZK
- MIP
- Probabilistically Checkable Proofs (PCP)
Probabilistically Checkable Proofs (PCP)
The PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).
The PCP theorem says that for some universal constant K, for every n, any mathematical proof for a statement of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof.
Used a.o. in SNARKS.
- PCP - Wikipedia
- A type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability.
- A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs.
- However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.
Arithmetic
Counting, log, exp, ...
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.
Logarithm and exponentiation
Logarithm is the inverse function to exponentiation. The logarithm of a number x to the base b is the exponent to which b must be raised, to produce x.
For example, since 1000 = 10**3, the logarithm base 10 of 1000 is 3, or log10 (1000) = 3.
The logarithm of x to base b is denoted as logb(x), or without the explicit base, log x, when no confusion is possible, or when the base does not matter such as in big O notation.
The logarithm base 10 is called the decimal or common logarithm and is commonly used in science and engineering. The natural logarithm has the number e ≈ 2.718 as its base; its use is widespread in mathematics and physics, because of its very simple derivative. The binary logarithm uses base 2 and is frequently used in computer science.
Logarithms were introduced by John Napier in 1614 as a means of simplifying calculations. They were rapidly adopted by navigators, scientists, engineers, surveyors and others to perform high-accuracy computations more easily. Using logarithm tables, tedious multi-digit multiplication steps can be replaced by table look-ups and simpler addition. This is possible because the logarithm of a product is the sum of the logarithms of the factors:
- Logarithm - Wikipedia
- Logarithm with e as base - Wikipedia
- The natural logarithm of x is the power to which e would have to be raised to equal x.
- For example, ln 7.5 is 2.0149..., because e2.0149... = 7.5
- Euler's number e - Wikipedia
- is approximately equal to 2.71828
- is the base of natural logarithms
- Exponentiation - Wikipedia
Modular arithmethic
The integers modulo a prime are a finite field.
Basics
- Modular arithmetic developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, 1801
- Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (that is, if there is an integer k such that a − b = kn).
- The modulo operation: the notation b mod n (without parentheses) refers to the modulo operation. Indeed, b mod n denotes the unique integer a such that 0 ≤ a < n and a ≡ b (mod n)(that is, the remainder of b when divided by n
- The congruence equation: the notation a ≡ b (mod n), where the parentheses mean that (mod n) applies to the entire equation, not just to the right-hand side (here, b).
- Given an integer n > 1, called a modulus, a ≡ b (mod n) if n is a divisor of their difference (if there is an integer k such that a − b = k.n)
- Reduction: 9 (mod 2) ≡ 1 (mod 2) (there is an integer k(=4) such that 9-1 = k.2
- Reduction: 9 (mod 2) ≡ 1 (mod 2) (there is an integer k(=4) such that 9-1 = k.2
- Reduction: 8 (mod 2) ≡ 0 (mod 2) (there is an integer k(=4) such that 8-0 = k.2
- Planetcalc - all kinds of calculators including for modular arithmethic
- Observation: 7-5=2, 5-7=-2 7 ≡ 5 (mod 2) because 7-5=2, (2 mod 2) = -4 | 2
- In modulus 12, one can assert that 38 ≡ 14 (mod 12) because 38 − 14 = 24 (a multiple of 12, with k=2). Alternatively, 14 ≡ 38 (mod 12) because 14 − 38 = -24 (also a multiple of 12, with k=-2).
- Another way to express this is to say that both 38 and 14 have the same remainder 2, when divided by 12.
- More examples: 8 mod 4 ≡ 0, 7 mod 2 ≡ 1
- The definition of congruence also applies to negative values. For example:
- 2 ≡ − 3 (mod 5) because -3 -2 | 5 (the notation (mod 5) at the end of the expression means mod 5 applies to both sides of the equation)
- − 8 ≡ 7 (mod 5) because 7 - (-8) = 15 | 5
- − 3 ≡ − 8 (mod 5) because -8 - (-3) = 5 | 5
- 1 ≡ − 3 (mod 2) because -3 -1 = -4 | 2
- 330 ≡ -1 (mod 331) because -1 - 330 = -331 | 331
- Fermat's little theorem
- If p is a prime number, then for any integer a, the number ap − a is an integer multiple of p.
- Expressed otherwise: ap ≡ a mod p
- Also, if a is not divisible by p, Fermat's little theorem is equivalent to the statement that ap − 1− 1 is an integer multiple of p.
- Expressed otherwise: ap-1 ≡ 1 mod p
- Root of unity modulo n - Wikipedia and quite a few other calculators
- A kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation (or congruence) x k ≡ 1 ( mod n ).
- If k is the smallest such exponent for x, then x is called a primitive kth root of unity modulo n.
- Modular arithmetic calculator and quite a few other calculators
p-adic numbers
- p-adic number - Wikipedia
- the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems.
- The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value. In particular, two p-adic numbers are considered to be close when their difference is divisible by a high power of p: the higher the power, the closer they are.
- This property enables p-adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles
- p-adic valuation - Wikipedia
- the p-adic valuation or p-adic order of an integer n is the exponent of the highest power of the prime number p that divides n. It is denoted νp(n) Equivalently, νp(n) is the exponent to which p in the prime factorization of n.
Calculus
Basics
Calculus is the study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations.
- Calculus - Wikipedia - two major branches
- Differential calculus concerns instantaneous rates of change, and the slopes of curves.
- Integral calculus concerns accumulation of quantities, and areas under or between curves.
- These two branches are related to each other by the fundamental theorem of calculus, and they make use of the fundamental notions of convergence of infinite sequences and infinite series to a well-defined limit.
Differentiation has applications in nearly all quantitative disciplines.
In physics,
- the derivative of the displacement of a moving body with respect to time is the velocity of the body,
- and the derivative of the velocity with respect to time is acceleration.
See
Integration
Process calculus
Linear algebra
Basics
Linear algebra concerns
- linear equations such as a1x1 + ⋯ + anxn = b ,
- linear maps such as ( x1 , … , xn ) ↦ a 1 x1 + ⋯ + a n xn ,
and their representations in vector spaces and through matrices.
Linear equations
And solving them, see
Vectors and vector spaces
A vector space (also called a linear space) is a set whose elements (vectors), may be added together and multiplied by numbers called scalars. Scalars are often real numbers, but can be complex numbers or, more generally, elements of any field.
The operations of vector addition and scalar multiplication must satisfy certain requirements, called vector axioms. The terms real vector space and complex vector space are often used to specify the nature of the scalars: real coordinate space or complex coordinate space.
Vector basics
A vector is a term that refers colloquially to some quantities that cannot be expressed by a single number (a scalar), or to elements of some vector spaces.
Historically, vectors were introduced in geometry and physics (typically in mechanics) for quantities that have both a magnitude and a direction, such as displacements, forces and velocity. Such quantities are represented by geometric vectors in the same way as distances, masses and time are represented by real numbers.
The term vector is also used, in some contexts, for tuples, which are finite sequences of numbers of a fixed length.
Vector spaces basics
A vector space (also called a linear space) is a set whose elements, often called vectors, may be added together and multiplied ("scaled") by numbers called scalars.
Both geometric vectors and tuples can be added and scaled, and these vector operations led to the concept of a vector space, which is a set equipped with a vector addition and a scalar multiplication that satisfy some axioms generalizing the main properties of operations on the above sorts of vectors.
- A vector space formed by geometric vectors is called a Euclidean vector space
- Euclidean space is the fundamental space of geometry, intended to represent physical space. In Euclid's Elements it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.
- Ancient Greek geometers introduced Euclidean space for modeling the physical space. Their work was collected by the ancient Greek mathematician Euclid in his Elements, with the great innovation of proving all properties of the space as theorems, by starting from a few fundamental properties, called postulates, which either were considered as evident (for example, there is exactly one straight line passing through two points), or seemed impossible to prove (parallel postulate).
- After the introduction at the end of 19th century of non-Euclidean geometries, the old postulates were re-formalized to define Euclidean spaces through axiomatic theory. Another definition of Euclidean spaces by means of vector spaces and linear algebra has been shown to be equivalent to the axiomatic definition. It is this definition that is more commonly used in modern mathematics. In all definitions, Euclidean spaces consist of points, which are defined only by the properties that they must have for forming a Euclidean space.
- There is essentially only one Euclidean space of each dimension; that is, all Euclidean spaces of a given dimension are isomorphic. Therefore, in many cases, it is possible to work with a specific Euclidean space, which is generally the real n-space Rn, equipped with the dot product. An isomorphism from a Euclidean space to Rn associates with each point an n-tuple of real numbers which locate that point in the Euclidean space and are called the Cartesian coordinates of that point.
- As from the early 19th century, other self-consistent non-Euclidean geometries were discovered.
- An implication of Albert Einstein's theory of general relativity is that physical space itself is not Euclidean, and Euclidean space is a good approximation for it only over short distances (relative to the strength of the gravitational field).
- a vector space formed by tuples is called a coordinate vector space.
- The simplest example of a vector space over a field F is the field F itself (as it is an abelian group for addition, a part of the requirements to be a field), equipped with its addition (It becomes vector addition.) and multiplication (It becomes scalar multiplication.). More generally, all n-tuples (sequences of length n) ( a1 , a2 , … , an) of elements ai of F form a vector space that is usually denoted Fn and called a coordinate space. The case n = 1 is the above-mentioned simplest example, in which the field F is also regarded as a vector space over itself.
Many vector spaces are considered in mathematics, such as extension field, polynomial rings, algebras and function spaces. The term vector is generally not used for elements of these vectors spaces, and is generally reserved for geometric vectors, tuples, and elements of unspecified vector spaces (for example, when discussing general properties of vector spaces).
- Vector space - Wikipedia
- A vector space over a field F is a non-empty set V together with two binary operations that satisfy the eight axioms listed below. In this context, the elements of V are commonly called vectors, and the elements of F are called scalars.
- The first operation, called vector addition or simply addition assigns to any two vectors v and w in V a third vector in V which is commonly written as v + w, and called the sum of these two vectors.
- The second operation, called scalar multiplication,assigns to any scalar a in F and any vector v in V another vector in V, which is denoted av.
- The eight operations:
- Associativity of vector addition, u + (v + w) = (u + v) + w
- Commutativity of vector addition, u + v = v + u
- Identity element of vector addition, There exists an element 0 ∈ V, called the zero vector, such that v + 0 = v for all v ∈ V.
- Inverse elements of vector addition, For every v ∈ V, there exists an element −v ∈ V, called the additive inverse of v, such that v + (−v) = 0.
- Compatibility of scalar multiplication with field multiplication, a(bv) = (ab)v
- Identity element of scalar multiplication, 1v = v, where 1 denotes the multiplicative identity in F.
- Distributivity of scalar multiplication with respect to vector addition, a(u + v) = au + av
- Distributivity of scalar multiplication with respect to field addition, (a + b)v = av + bv
Dot product
The dot product or scalar product is an algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors), and returns a single number.
- In Euclidean geometry, the dot product of the Cartesian coordinates of two vectors is widely used. It is the product of the Euclidean magnitudes of the two vectors and the cosine of the angle between them. These definitions are equivalent when using Cartesian coordinates.
- In geometry, a Cartesian coordinate system in a plane specifies each point uniquely by a pair of real numbers called coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, called coordinate lines, coordinate axes or just axes (plural of axis). The point where they meet is called the origin and has (0, 0) as coordinates.
- Similarly, the position of any point in three-dimensional space can be specified by three Cartesian coordinates, which are the signed distances from the point to three mutually perpendicular planes. More generally, n Cartesian coordinates specify the point in an n-dimensional Euclidean space for any dimension n. These coordinates are the signed distances from the point to n mutually perpendicular fixed hyperplanes.
- Euclidean spaces are often defined by using vector spaces.
- In this case, the dot product is used for defining lengths (the length of a vector is the square root of the dot product of the vector by itself) and angles (the cosine of the angle between two vectors is the quotient of their dot product by the product of their lengths).
- It is often called the inner product of Euclidean space (even though it is not the only inner product that can be defined on Euclidean space).
- The dot product is the sum of the products of the corresponding entries of the two sequences of numbers.
- The name "dot product" is derived from the centered dot " · " that is often used to designate this operation; the alternative name "scalar product" emphasizes that the result is a scalar, rather than a vector (as with the vector product in three-dimensional space).
Dot product illustration
The dot product of two vectors a = [a1 , a2 , ⋯ , an] and b = [b1 , b2, ⋯ , bn] specified with respect to an orthonormal basis, is defined as: a.b = a1b1 + a2b2 + ⋯ + anbn
For instance, in three-dimensional space, the dot product of vectors [ 1, 3, −5] and [ 4, −2, −1] is: [ 1, 3, −5] ⋅ [ 4, − 2, −1] = (1 × 4) + (3 × −2) + (−5 × −1) = 4−6+5 = 3
Linear maps
A prototypical example that gives linear maps their name is a function f : R → R : x ↦ cx of which the graph is a line through the origin
The Weil pairing is a pairing (bilinear form, though with multiplicative notation) on the points of order dividing n of an elliptic curve E, taking values in nth roots of unity.
- Bilinear form - Wikipedia
- Is a bilinear map V × V → K on a vector space V (the elements of which are called vectors) over a field K (the elements of which are called scalars).
- In other words, a bilinear form is a function B : V × V → K that is linear in each argument separately:
- B(u+v, w) = B(u, w) + B(v, w)
- B(λu, v) = λB(u, v)
- B(u, v+w) = B(u, v) + B(u, w)
- B(u, λv) = λB(u, v)
The dot product (scalar product) on Rn is an example of a bilinear form.
Bilinear map
A bilinear map is a function combining elements of two vector spaces to yield an element of a third vector space, and is linear in each of its arguments. Matrix multiplication is an example.
Abstract algebra
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.
- Algebra - Wikipedia
- Elementary algebra deals with the manipulation of variables such as x as if they were numbers.
- Linear algebra, which deals with linear equations and linear mappings, is used for modern presentations of geometry, and has many practical applications (weather forecasting ...).
- Abstract algebra is the name given to the study of algebraic structures such as groups, rings, and fields, see below
- Abstract Algebra - great overview + Sage exercises
Polynomials
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.
Lagrange interpolation
The Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.
Lagrange normal basis
Lagrange theorem on how frequently a polynomial over the integers evaluates to a multiple of a fixed prime
Lagrange theorem - Wikipedia
Polynomials over rings and fields
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.
Sets and cosets
Magmas
Basics
A magma, binar, or groupoid consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.
Groups
Basics
- Group Properties Wiki - beta - but interesting
- Group - is
- a set and
- an operation that combines any two elements of the set to produce a third element of the set,
- in such a way that the operation is associative,
- an identity element exists and
- every element has an inverse
- Otherwise said: Group G is a set with 1 binary operation * such that following properties holds: * is associative, there is an identity element, each element has an inverse element
- Example: the integers together with the addition operation form a group.
Relevant for cryptography (Ben Lynn's thesis):
- Diffie-Hellman depends on cyclic groups with particular properties.
- RSA depends on groups that are not cyclic and require that the order of the group is unknown to the attacker.
Using representation theory group elements can be represented as linear transformations of vector spaces.
Features of a single group
- Abelian: if a * b = b * a then the group is called abelian or commutative
- Cyclic: if there exists a generator g such that for any element b there is an integer j such that gj = b then the group is cyclic
- For implementing cyclic groups, two settings are possible: finite fields and elliptic curves.
- Bilinear maps, or pairings, give cyclic groups additional properties.
- Order of a group: the number of elements in a finite group is called its order, |G|
- Furthermore:
- The subgroup of G consisting of all powers of the element a is called the subgroup generated by a, denoted by <a>
- In case the element a is a generator of the group (ref g supra), then <a> (the subgroup generated by a) is simply the group
- And <a> is of finite order k if is k is the least positive integer such that ak = e, the identity element
Features of sets of groups
- Homomorphism: is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces) that preserves the operations of the structures.
- Homomorphisms of vector spaces are also called linear maps, and their study is the subject of linear algebra.
- Group homomorphism: given two groups, (G, ∗) and (H, ·), a group homomorphism from (G, ∗) to (H, ·) is a function h : G → H such that for all u and v in G it holds that h ( u ∗ v ) = h ( u ) ⋅ h ( v ) where the group operation on the left side of the equation is that of G and on the right side that of H.
Bilinear groups (i.e. groups where bilinear maps, or pairings, can be found)
From Groth16: 'We will work over bilinear groups (p, G1, G2 , GT, e, g, h) with the following properties:
- G1, G2, GT are groups of prime order p
- The pairing e : G1 × G2 → GT is a bilinear map
- g is a generator for G1 , h is a generator for G2, and e(g, h) is a generator for GT
- There are efficient algorithms for computing group operations, evaluating the bilinear map, deciding membership of the groups, deciding equality of group elements and sampling generators of the groups. We refer to these as the generic group operations.
- There are many ways to set up bilinear groups both as symmetric bilinear groups where G1 = G2 and as asymmetric bilinear groups where G1 is different from G2.
- Galbraith, Paterson and Smart [Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156(16):3113–3121, 2008.] classify bilinear groups as
- Type I where G1 = G2,
- Type II where there is an efficiently computable non-trivial homomorphism Ψ : G2 → G1, and
- Type III where no such efficiently computable homomorphism exists in either direction between G1 and G2. Type III bilinear groups are the most efficient type of bilinear groups and hence the most relevant for practical applications.
More:
- Bilinear groups - consists of three groups G1, G1 and GT as well as a bilinear pairing function e.
Isogeny groups (i.e. a morphism that is surjective and has a finite kernel)
An isogeny is a morphism of algebraic groups (also known as group varieties) that is surjective and has a finite kernel.
- A surjective function (also known as surjection, or onto function) is a function f such that every element y can be mapped from some element x such that f(x) = y. In other words, every element of the function's codomain is the image of at least one element of its domain. It is not required that x be unique; the function f may map one or more elements of X to the same element of Y.
- The kernel of a homomorphism (function that preserves the structure) is generally the inverse image of 0 (except for groups whose operation is denoted multiplicatively, where the kernel is the inverse image of 1).
- An important special case is the kernel of a linear map. The kernel of a matrix, also called the null space, is the kernel of the linear map defined by the matrix.
- For kernel in linear algebra see https://en.wikipedia.org/wiki/Kernel_(linear_algebra)
- The kernel of a homomorphism is reduced to 0 (or 1) if and only if the homomorphism is injective, that is if the inverse image of every element consists of a single element. This means that the kernel can be viewed as a measure of the degree to which the homomorphism fails to be injective.
- For some types of structure, such as abelian groups and vector spaces, the possible kernels are exactly the substructures of the same type. This is not always the case, and, sometimes, the possible kernels have received a special name, such as normal subgroup for groups and two-sided ideals for rings.
- Kernels allow defining quotient objects (also called quotient algebras in universal algebra, and cokernels in category theory). For many types of algebraic structure, the fundamental theorem on homomorphisms (or first isomorphism theorem) states that image of a homomorphism is isomorphic to the quotient by the kernel.
If the groups are abelian varieties, then any morphism f : A → B of the underlying algebraic varieties which is surjective with finite fibres is automatically an isogeny, provided that f(1A) = 1B. Such an isogeny f then provides a group homomorphism between the groups of k-valued points of A and B, for any field k over which f is defined.
The terms "isogeny" and "isogenous" come from the Greek word ισογενη-ς, meaning "equal in kind or nature". The term "isogeny" was introduced by Weil; before this, the term "isomorphism" was somewhat confusingly used for what is now called an isogeny.
Rings
Basics
- Ring R - set with 2 binary operations (+ and *) such that R is abelian with respect to +, * is associative, and + and * are distributive
- If there is a multiplicative identity the ring is called a ring with identity
- A ring is called commutative if * is commutative
- A ring is called an integral domain if it is a commutative ring with identiy e ¬ = 0 in which ab=0 implies a=0 or b=0
- A ring is called a division ring if the nonzero elemnts form a group under *
- A commutative division ring is called a field
Examples
The four common rings:
- the integers, referred to as ZZ or Z/nZ or Zn or Zn
- the rationals
- the reals
- the complex numbers
Characteristics of a ring
The characteristic of a ring R is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive identity the ring is said to have characteristic zero.
Ideal of a ring (subset of its elements)
An ideal of a ring R is a special subset of its elements. Ideals generalise certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any integer (even or odd) results in an even number; these closure and absorption properties are the defining properties of an ideal. An ideal can be used to construct a quotient ring in a way similar to how, in group theory, a normal subgroup can be used to construct a quotient group.
Illustrations:
- Among the integers, the ideals correspond one-for-one with the non-negative integers: in this ring, every ideal is a principal ideal consisting of the multiples of a single non-negative number.
- In other rings the ideals may not correspond directly to the ring elements, and certain properties of integers, when generalized to rings, attach more naturally to the ideals than to the elements of the ring. For instance, the prime ideals of a ring are analogous to prime numbers, and the Chinese remainder theorem can be generalized to ideals.
Principal ideal of a ring (subset of its elements)
In ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R .
Note: the term also has another, similar meaning in order theory.
Divisability of a ring, divisors, left and right divisors
The notion of a divisor arose within the arithmetic of whole numbers. With the development of abstract rings, of which the integers are the archetype, the original notion of divisor found a natural extension.
Divisibility is a useful concept for the analysis of the structure of commutative rings because of its relationship with the ideal structure of such rings.
Let R be a ring, and let a and b be elements of R.
- If there exists an element x in R with ax = b, one says that a is a left divisor of b and that b is a right multiple of a.
- Similarly, if there exists an element y in R with ya = b, one says that a is a right divisor of b and that b is a left multiple of a.
- One says that a is a two-sided divisor of b if it is both a left divisor and a right divisor of b; the x and y above are not required to be equal.
When R is commutative, the notions of left divisor, right divisor, and two-sided divisor coincide, so one says simply that a is a divisor of b, or that b is a multiple of a, and one writes a ∣ b.
Zero divisors (in a ring or a semi-group with zero element)
A zero divisor is a non-zero element such that the product with some non-zero element is zero (weird name choice). An element a is called a left (right) divisor of zero if ab=0 (ba=0) for at least one b≠0.
The only zero divisor of the ring Z of integers is 0.
Polynomial rings
A polynomial ring is a ring formed from the set of polynomials in one or more indeterminates (also called variables) with coefficients in another ring, often a field.
Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers.
The polynomial ring, K[X], in X over a field (or, more generally, a commutative ring) K can be defined in several equivalent ways. One of them is to define K[X] as the set of expressions, called polynomials in X.
Univariate polynomial rings - single variable (indeterminate)
The polynomial ring, K[X], in X over a commutative ring (or over a field) K can be defined as the set of expressions, called polynomials in X, of the form p = p0 + p1 X + p2 X2 + ⋯ + pm-1Xm−1 + pmXm, where p0, p1, p2, the coefficients of p, are elements of K, pm ≠ 0 if m > 0, and X, X2, …, are symbols, which are considered as "powers" of X, and follow the usual rules of exponentiation for any nonnegative integers k and l. The symbol X is called an indeterminate or variable.
Fields
Basics
It can be observed that while composites of the form m.n do not lead to fields, e.g. Z(15) is not a field.
But numbers such as pk (which could potentially also be called composites of the form p.p) do lead to fields. F(p^k) is a field.
Definition:
- Set F with 2 binary operations (+ and *)
- Has two distinguished elements:
- zero element 0
- identity element e such that e ¬ = 0
- Is an abelian group with regard to + with 0 as identity element
- The elements of F that are ¬ = 0 form an abelian group with regard to *, with e as identity element - requirement for multiplicative inverse???
- The distributive laws hold on + and *
Notation
N. Smart's book 'Cryptography Made Simple':
- Z/NZ = {0, ..., N-1}, Z/NZ is the set of remainders modulo N
- An alternative notation for Z/NZ is ZN
- The set of intervertable elements in Z/NZ are (Z/NZ)* = { x ∈ Z/NZ: gcd(x,N)=1}
- In case N is a prime p we have (Z/pZ)* = {1, ..., p-1}
- Fp = Z/pZ = Zp = {0, ..., p-1}, which is a finite field of characteristic p
- Fp* = (Z/pZ)* = {1, ..., p-1}
Selective fields
- Composites do not yield a field because there will be numbers for which there is no multiplicative inverse:
- Fn e.g. Z15 is not a field. The main reason why Zn is only a commutative ring and not a finite field is because not every element in Zn is guaranteed to have a multiplicative inverse. An element a of Zn does not have a multiplicative inverse if a is not relatively prime to the modulus n. E.g. in Z15 5 is not relatively prime to the modulus 15. A multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1.
- See Lidl and Niederreiter Chapter 10 for calculations in fields GF(22) ... GF(23)...GF(112)
- F8 = F23 is a finite field
- Fp = Z/pZ = Zp = {0,1,...,p-1} is a finite field
- F9 = F32 is a field of 9 elements. F9 is an extension of F3 of degree 2.
- Fields of characteristic 2 are popular because they allow efficient arithmetic for a.o. AES and EC
Creation of finite fields
Lidl and Niederreiter describe three ways to represent elements of finite fields:
- Regard Fpk as an extension of Fp, using polynomials and polynomial operations.
- Since Fq = Fpk is the (q-1)st cyclotomic field over Fp we can construct it by finding the decomposition of the (q-1)st cyclotomic polynomial Qq-1 in Fp[x] into irreducible factors in Fp[x] which are all of the same degree.
- By using companion matrices. Calculations can then be carried out by the usual rules of matrix algebra.
Also: see https://www.doc.ic.ac.uk/~mrh/330tutor/ch04s02.html
One way to construct a finite field Fpk with k >1 is using the polynomial basis. The field is constructed as a set of pk polynomials along with two polynomial operations.
Polynomials are specified as f(x) = p = p0 + p1 x + p2 x2 + ⋯ + p m-1 xm−1 + pmxm,
The highest exponent of x is the degree of the polynomial.
In a polynomial, p0, p1, ... are called coefficients. If the coefficients are taken from a field F, then we say it is a polynomial over F.
Polynomials over field GF(p)
With polynomials over field GF(p), you can add and multiply polynomials just like you have always done but the coefficients need to be reduced modulo p.
We can add, subtract polynomials by combining the terms in the polynomials with the same powers. We can multiply and divide (in which case there might be a remainder).
If a polynomial is divisible only by itself and constants, then we call this polynomial irreducible. Irreducible polynomials have properties similar to prime numbers.
Similar to integers, you can do modular arithmetic with polynomials over a field. Now the operands and modulus are polynomials. Always remember there are two moduli involved: a polynomial modulus and an integer modulus. You need to reduce the result from the polynomial operations by modulo the polynomial modulus and then reduce the coefficients modulo the integer modulus.
Let f(x) and g(x) be two polynomials over a field F, of degrees n and m respectively, then there is a unique polynomial r(x) of degree smaller than m and another unique polynomial h(x), both over F, such that f(x) = h(x)*g(x)+r(x). The polynomial r(x) is called the remainder of f(x) modulo g(x). For polynomials a(x), b(x) and g(x) which are over the same field, we say a(x) is congruent to b(x) modulo g(x) written a(x) ≡ b(x) mod g(x), if m(x) divides a(x)-b(x).
Polynomials over field GF(pm)
If the modulus g(x) is an irreducible polynomial of degree m over GF(p), then the finite field GF(pm) can be constructed by the set of polynomials over GF(p) whose degree is at most m-1, where addition and multiplication are done modulo g(x).
For example, the finite field GF(32) can be constructed as the set of polynomials whose degrees are at most 1, with addition and multiplication done modulo the irreducible polynomial x2+1 (you can also choose another modulus, as long as it is irreducible and has degree 2).
Polynomials over field GF(2m)
Finite fields of order 2m are called binary fields or characteristic-two finite fields. They are of special interest because they are particularly efficient for implementation in hardware, or on a binary computer. The elements of GF(2m) are binary polynomials, i.e. polynomials whose coefficients are either 0 or 1.
Order of a field (number of its elements)
The order (or size) of a finite field is its number of elements.
The order of a finite field is always a prime or a power of a prime (Why? Birkhoff and Mac Lane 1996).
Fields of prime order, Fp
- The simplest examples of finite fields are the fields of prime order: for each prime number p, the prime field of order p, Fp, may be constructed as the integers modulo p, Z/pZ.
- The elements of the prime field of order p may be represented by integers in the range {0, ..., p − 1}.
- For a finite field Fp = Z/pZ = Zp = {0, ..., p-1}, its order is p.
- The sum, the difference and the product are the remainder of the division by p of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm.
If the field is called Fq but q is simply a prime, then any field with q elements is isomorphic to the integers mod q. Addition and multiplication are defined just as in the integers, except you always take the remainder by q after you add or multiply.
Fields of prime power order, Fpk = Fq
- A finite field of order q exists if and only if q is a prime power pk (where p is a prime number and k is a positive integer). (Why? Birkhoff and Mac Lane 1996).
- If q = pk, all fields of order q are isomorphic. Moreover, a field cannot contain two different finite subfields with the same order. One may therefore identify all finite fields with the same order, and they are unambiguously denoted Fq, Fq or GF(q).
- In a field of order q = pk, adding p copies of any element always results in zero; that is, the characteristic of the field is p.
See https://www.johndcook.com/blog/2022/09/21/field-of-order-9/ Multiplication in a field of 9 elements (9 = 32)is not simply multiplication mod 9. You need an irreducible polynome as well.
Arithmetic in prime power fields:
- If q = pk for some prime p and positive integer k, we define elements of our field to be polynomials of degree k–1.
- F(9) = F(32), the field with 9 elements, can be defined as polynomials of the form ax + b where a and b are integers mod 3, i.e. a and b can take on the values 0, 1, or 2.
- Addition in F(9) corresponds to polynomial addition, with the understanding that the coefficients are added mod 3. So, for example,
(2x + 1) + (x + 0) = 1 because the leading coefficient is 2 + 1, which reduces to 0 mod 3.
- For multiplication in F(9) we take the remainder after dividing by a fixed irreducible polynomial of degree k.
In a finite field of order q, the polynomial Xq − X has all q elements of the finite field as roots. The non-zero elements of a finite field form a multiplicative group. This group is cyclic, so all non-zero elements can be expressed as powers of a single element called a primitive element of the field. (In general there will be several primitive elements for a given field.)
When and why to use prime fields versus prime power fields seems to be an implementation issue.
Characteristic of a field (number of time the multiplicative identity must be added to the the additive identity)
The expression 'characteristics' carries over from the rings. Recall that the characteristic of a ring R is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0).
The characteristic of any field is either 0 or a prime number. A field of non-zero characteristic is called a field of finite, positive or prime characteristic.
The characteristic of any field with positive characteristic must be prime.
- For fields with a positive characteristic, the roots belong to a finite field, and, conversely, every nonzero element of a finite field is a root of unity.
- Any algebraically closed field contains exactly n nth roots of unity, except when n is a multiple of the (positive) characteristic of the field.
Sidebar: roots of a finite field ...
Fields of prime characteristic
The finite field GF(p n) has characteristic p.
There exist infinite fields of prime characteristic. For example, the field of all rational functions over Z/pZ, the algebraic closure of Z/pZ or the field of formal Laurent series Z/pZ.
The size of any finite ring of prime characteristic p is a power of p. Since in that case it contains Z/pZ it is also a vector space over that field, and from linear algebra we know that the sizes of finite vector spaces over finite fields are a power of the size of the field. This also shows that the size of any finite vector space is a prime power.
Normal basis of a field
A normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.
See https://en.wikipedia.org/wiki/Normal_basis
Fields and polynomials
Extension fields and subfields
A field extension is a pair of fields K ⊆ L such that the operations of K are those of L restricted to K. In this case, L is an extension field of K and K is a subfield of L.
For example, under the usual notions of addition and multiplication
- the field of complex numbers C is an extension field of the field of real numbers R;
- R is a subfield of the field of complex numbers Q,
- and C/Q is also a field extension.
See
Splitting fields
The splitting field of a polynomial is the smallest field containing all roots of that polynomial. Otherwise said, a splitting field of a polynomial with coefficients in a field is the smallest field extension of that field over which the polynomial splits, i.e., decomposes into linear factors.
Any finite field GF(q), where q=pn, is the splitting field of the polynomial xq−x over the prime subfield GF(p) ⊂ GF(q).
Cyclotomic fields
A cyclotomic field is a number field obtained by adjoining a complex root of unity to Q, the field of rational numbers.
Cyclotomic fields played a crucial role in the development of modern algebra and number theory because of their relation with Fermat's Last Theorem. It was in the process of his investigations of the arithmetic of these fields (for prime n) – and more precisely, because of the failure of unique factorization in their rings of integers – that Ernst Kummer first introduced the concept of an ideal number and proved his celebrated congruences.
Fields of p-adic numbers
P-adic numbers
The p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems. The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value.
In particular, two p-adic numbers are considered to be close when their difference is divisible by a high power of p: the higher the power, the closer they are.
This property enables p-adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles.
The p-adic integers are the p-adic numbers with a nonnegative valuation.
A p-adic integer can be represented as a sequence x = ( x1 mod p, x2 mod p2, x3 mod p3 , … ) of residues xe mod pe for each integer e, satisfying the compatibility relations xj ≡ xj (mod pi ) for i < j.
Every integer is a p-adic integer (including zero, since 0 < ∞. The rational numbers of the form n/d pk with d coprime with p and k ≥ 0 are also p-adic integers (because d has an inverse mod pe for every e).
P-adic numbers ring and field
The p-adic integers form a commutative ring, denoted Zp (difference in notation with regular Zp?) that has the following properties.
- It is an integral domain, since it is a subring of a field, or since the first term of the series representation of the product of two non zero p-adic series is the product of their first terms.
- The units (invertible elements) of Zp are the p-adic numbers of valuation zero.
- It is a principal ideal domain, such that each ideal is generated by a power of p.
- It is a local ring of Krull dimension one, since its only prime ideals are the zero ideal and the ideal generated by p, the unique maximal ideal.
- It is a discrete valuation ring, since this results from the preceding properties.
- It is the completion of the local ring Z (p) = { n/d ∣ n, d ∈ Z, d ∉ pZ} which is the localization of Z at the prime ideal pZ.
The last property provides a definition of the p-adic numbers that is equivalent to the above one: the field of the p-adic numbers is the field of fractions of the completion of the localization of the integers at the prime ideal generated by p.
Applications of finite fields
Popular fields in cryptography:
- Fields of the integers modulo a large prime, noted as Fp = Z/pZ = Zp = {0, ..., p-1}
- Recall that adding * removes the zero, i.e. Fp* = {1, ..., p-1}
- Fields of characteristic 2, because they are efficiently to implement.
Definition of a finite field of characteristic 2:
- Pick an irreducible polynomial f(x) over F2 of degree n.
- The field is defined as F2n = F2[x]/f(x), i.e. binary poloynomials modulo f(x)
- Field elements are represented as strings which represent the a binary polynomial.
- E.g. the string 101010111 represents the polynomial x8 + x6 + x4 + x2 + x + 1.
The difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol.
Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or BCH code. The finite field almost always has characteristic of 2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of GF(28).
Roots
Roots
- Root of unity - Wikipedia
- Any complex number that yields 1 when raised to some positive integer power n.
- Can be defined in any field.
- If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers.
Quadratic residues, Legendre and Jacobi symbols
QR
For an introduction refer to the HAC Section 3.4.
There is a significant difference finding QRs modulo a prime (randomised algorithm exists) versus a composite (if the factors are unknown, this is the Quadratic Residuity Problem).
- QR - Wikipedia integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that x2 ≡ q (mod n) - finding x may be hard
- Euler's criterion - Wikipedia
- Is a formula for determining whether an integer is a quadratic residue modulo a prime via a(p-1)|2 mod p
- Let p be an odd prime and a be an integer coprime to p. Then:
- a(p-1)|2 ≡ 1 mod p if there is an integer x such that a ≡ x2 mod p
- a(p-1)|2 ≡ -1 mod p otherwise
- Illustration 1: which numbers are squares modulo 17 (quadratic residues modulo 17)? We can manually calculate it as:
- 12 = 1
- 22 = 4
- 32 = 9
- 42 = 16
- 52 = 25 ≡ 8 (mod 17)
- 62 = 36 ≡ 2 (mod 17)
- 72 = 49 ≡ 15 (mod 17)
- 82 = 64 ≡ 13 (mod 17).
- So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}.
- Illustration 2: let a = 17. For which primes p is 17 a quadratic residue? We can test prime p's manually given the Eurler formula a(p-1)|2 mod p.
- Consider p = 3, then 17(3 − 1)|2 = 171 ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.
- Consider p = 13, then 17(13 − 1)|2 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 4.
- Law of quadratic reciprocity - Wikipedia
- gives conditions for the solvability of quadratic equations modulo prime numbers
- allows to determine whether there is an integer solution for any quadratic equation of the form x2 ≡ a mod p for an odd prime p, that is, to determine the "perfect squares" modulo p.
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
- Legendre symbol - Wikipedia - defined to proof the law of quadratic reciprocity
- Legendre symbol - prime p and integer a
- Let p be an odd prime number. An integer a is a quadratic residue modulo p if it is congruent to a perfect square modulo p and is a quadratic non-residue modulo p otherwise. The Legendre symbol is a function of a and p defined as
- +1 if a is a QR modulo p and a not ≡ 0 mod p
- -1 if a a quadratic non-residue modulo p
- 0 if a is ≡ 0 mod p
Jacobi - [composite] integer n and integer a
- Jacobi symbol integer n and integer a - (generalisation of Legendre) - Wikipedia - usefull a.o. in primality testing and integer factorisation
- Let n be any positive odd integer n (which may be composite). For any integer a, the Jacobi symbol (a/n) is defined as the product of the Legendre symbols corresponding to the prime factors of n
- +1 if a is a QR modulo p and a not ≡ 0 mod p
- -1 if a a quadratic non-residue modulo p
- 0 if a is ≡ 0 mod p
Elliptic curve
See Lynn's Ph.D. thesis.
Basics
An elliptic curve is a smooth, projective, algebraic curve of genus one (one 'hole), on which there is a specified point O.
An elliptic curve is defined over a field K and describes points in K x K, the Cartesian product of K with itself. If the field's characteristic is different from 2 and 3, then the curve can be described as a plane algebraic curve which consists of solutions (x, y) for y2 = x3 + a x + b for some coefficients a and b in K.
- Genus - Wikipedia In mathematics, genus (PL: genera) has a few different, but closely related, meanings. Intuitively, the genus is the number of "holes" of a surface. A sphere has genus 0, while a torus (doughnut)has genus 1.
- Smoothness - Wikipedia - Smoothness of a function is a property measured by the number of continuous derivatives it has over some domain, called differentiability class.[1] At the very minimum, a function could be considered smooth if it is differentiable everywhere (hence continuous). At the other end, it might also possess derivatives of all orders in its domain, in which case it is said to be infinitely differentiable and referred to as a C-infinity function (or C ∞ function)
Introductions:
EC's embedding degree
See 'Constructing Elliptic Curves with Prescribed Embedding Degrees' - Barreto, Lynn, Scott.
Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree for most elliptic curves is
enormous, and the few previously known suitable elliptic curves have embedding degree k less or equal to 6.
A subgroup G of (the group of points of) an elliptic curve E(Fq ) is said to have embedding degree or security multiplier k if the subgroup order r divides qk − 1, but does not divide qi − 1 for all 0 < i < k. The Tate pairing [3,9,11] (or the Weil pairing [15,18,25]) maps the discrete logarithm in G to the discrete logarithm in Fqk , and this is the basis for the Frey-Ruck attack [10].
An important open problem in pairing-based cryptography [5,6,12,14,22,23,27,29] is to build curves containing a subgroup with embedding degree k that is at once big enough to prevent the Frey-Ruck attack, but small enough that the Tate pairing is efficiently computable, which in turn means that arithmetic in Fqk is feasible. The embedding degree is known to be usually enormous [2,19], and for a long time, the only elliptic curves known to admit subgroups with reasonable k were supersingular curves, particularly over F3m where k = 6 [18]. Such curves are constructed over fields of low characteristic, making them more susceptible to discrete logarithm algorithms [24].
Weierstrass equation
This is a traditional way to specify an EC as y2= x3+ ax + b, in which form the curve always contains exactly one point at infinity.
While this is commonly referred to as the Weierstrass equation, it is a simplification of the full form, which is specified as follows.
Source: https://www.lmfdb.org/knowledge/show/ec.weierstrass_coeffs
A Weierstrass equation or Weierstrass model over a field k is a plane curve E of the form y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6, with a1, a2, a3, a4, a5, a6 in k.
The Weierstrass coefficients of this model E are the five coefficients ai. These are often displayed as a list [a_1, a_2, a_3, a_4, a_6].
It is common not to distinguish between the affine curve defined by a Weierstrass equation and its projective closure, which contains exactly one additional point at infinity, [0:1:0].
A Weierstrass model is smooth if and only if its discriminant is nonzero. In this case, the plane curve E together with the point at infinity as base point, define an elliptic curve defined over k.
Singularity
Curves can be singular, non-singular (cryptocurves), supersingular.
Given the equation y2 = x3 + a x + b , the discriminant of the cubic in x is 4a3 + 27b2.
- If the discriminant = 0, then the curve has a repeated root, and the curve is singular.
- If the discriminant ≠ 0, then the curve has distinct roots, and the curve is non-singular, which is good for crypto.
- supersingular is a type of non-singular (sic)
Background:
- Singular curves - singularity - Wikipedia
- A singularity is a point at which a given mathematical object is not defined, or a point where the mathematical object ceases to be well-behaved in some particular way, such as by lacking differentiability or analyticity.
- For example, the function f(x) = 1/x has a singularity at x = 0, where the value of the function is not defined, as involving a division by zero.
- Non-singularity (useful for cryptography), which means that the curve has no cusps (A cusp is the most pointed end of a curve, referring to cusp (anatomy), a pointed structure on a tooth) or self-intersections.
-
- Supersingular curves - Wikipedia - are in fact non-singular
Hyperelliptic
- Hyperelliptic curve - Encyclopedia of Mathematics
- Hyperelliptic curve - Wikipedia
- n algebraic geometry, a hyperelliptic curve is an algebraic curve of genus g > 1, given by an equation of the form y2 + h(x)y = f(x)
where f(x) is a polynomial of degree n = 2g + 1 > 4 or n = 2g + 2 > 4 with n distinct roots, and h(x) is a polynomial of degree < g + 2 (if the characteristic of the ground field is not 2, one can take h(x) = 0).
Lynn: no implementations of PBC on hyperelliptic curves.
Embedding degree
Embedding degree k is ...
Well-known theorems
Hasse, on the number of points on an EC (called the trace of Frobenius). t = qk + 1 - #E (Fqk).
Weil.
Ways of specifying ECs
There are many ways of specifying an EC.
- The traditional way, using the (simplified) Weierstrass equation: y2= x3+ ax + b, in which form the curve always contains exactly one point at infinity
- Huff curves,
- Jacobi quartics,
- (twisted) Edwards curves.
Then there's the question whether a curve is suitable for cryptography. Useful curves include:
- IETF's analysis of pairing friendly curves - contains overview of PBC
- A BN curve, see https://link.springer.com/chapter/10.1007/11693383_22 (Barreto, Naehrig), is an instantiation of pairing-friendly curves proposed in 2005. A pairing over BN curves constructs optimal Ate pairings.
- A BLS curve, see https://link.springer.com/chapter/10.1007/3-540-36413-7_19 (Barreto, Lynn, Scott) is an instantiation of pairings proposed in 2002. Similar to BN curves, a pairing over BLS curves constructs optimal Ate pairings.
EC pairings
Refer also to pairing-based crypto.
See 'On the Selection of Pairing-Friendly Groups', Barreto, Lynn & Scott at https://link.springer.com/chapter/10.1007/978-3-540-24654-1_2 .
NIST: a pairing is a function that maps a pair of points on an elliptic curve into a finite field.
It does not work like first choose the groups and then find a bilinear map, but the other way round. All you can do is choose groups and function and then check IF your construction fulfills the definitions of pairings. Some basic properties have to "fit" (e.g. the orders of the groups need to be compatible).
Being able to create pairings on just any groups of your liking, would be a major algebraic breakthrough.
Weil pairing
Specification
Kaliska's Ph.D. thesis (Appendix 1) contains a clear description of the Weil pairing.
Also Lynn's Ph.D. thesis.
Calculation
In 1985 Miller found the MACSYMA algorithm for the calculation of the Weil pairing (described in Section 4.1), and wrote it up as a note which has never been published, though widely distributed and cited. Burt Kaliski devotes a chapter to this algorithm in his Ph.D. thesis - Appendix 1, B and was the first to implement it.
Using the Weil pairing to reduce the DLP to subexponential
Was used by Menezes, Okamoto and Vanstone ('MOV', 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.
Their method reduces the EC logarithm problem in a curve E over a finite field Fq to the discrete logarithm problem in a suitable extension field Fgk of Fg. This is achieved by establishing an isomorphism between <P>, the subgroup of E generated by P, and the subgroup of nth roots of unity in Fqk, where n denotes the order of P. The isomorphism is given by the Weil pairing.
Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.
Tate pairing
Specification
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.
Other pairings
TBD
Isogenous EC
See https://gkorpal.github.io/quantum/isogeny. Isogeny-based cryptography is a kind of elliptic-curve cryptography, whose security relies on (various incarnations of) the problem of finding an explicit isogeny between two given isogenous supersingular elliptic curves over a finite field Fq.
However, given an elliptic curve E in Weierstrass form over a finite field Fq and a point P on E of order n, one can compute a cyclic separable isogeny of degree n using Velu’s formulas in SageMath (implemented by D. Shumow in 2009).
Currently, quantum computers do not seem to make the isogeny-finding problem substantially easier. This contrasts with the standard discrete-logarithm based elliptic-curve cryptography which is not quantum-safe due to polynomial-time quantum algorithm by P. W. Shor from 1997.
See https://www.mariascrs.com/posts.html. SIDH, SIKE (NIST PQ).
Representation theory
Studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures.
A representation makes an abstract algebraic object more concrete by describing its elements by matrices and their algebraic operations (for example, matrix addition, matrix multiplication).
The theory of matrices and linear operators is well-understood, so representations of more abstract objects in terms of familiar linear algebra objects helps glean properties and sometimes simplify calculations on more abstract theories.
The algebraic objects amenable to such a description include groups, associative algebras and Lie algebras. The most prominent of these (and historically the first) is the representation theory of groups, in which elements of a group are represented by invertible matrices such that the group operation is matrix multiplication.
https://en.wikipedia.org/wiki/Representation_theory
Logic
Reasoning
- Inductive reasoning
- A method of reasoning in which the premises are viewed as supplying some evidence, but not full assurance, of the truth of the conclusion.
- It is also described as a method where one's experiences and observations, including what are learned from others, are synthesized to come up with a general truth.
- Many dictionaries define inductive reasoning as the derivation of general principles from specific observations (arguing from specific to general), although there are many inductive arguments that do not have that form
- Conclusions from inductive reasoning are probably, not certain
- Deductive reasoning
- Is the process of reasoning from one or more statements (premises) to reach a logical conclusion.
- Deductive reasoning links premises with conclusions.
- If all premises are true, the terms are clear, and the rules of deductive logic are followed, then the conclusion reached is necessarily true.
Intro and overview
Set theory and Z
Intro
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
- CZT - Community Z Tools, including LaTeX styles and parsers, typecheckers, etc
- czt-ide - Releases of standalone CZT IDE, based on Eclipse platform. Use it to author, develop and verify Z specifications.
- Download archived version for Windows 64 bits
- czt-ide-updates - Update sites for released CZT Eclipse plugins to be installed in your own Eclipse IDE.
- czt-jedit - Plugins for the jEdit text editor (www.jedit.org) adding support for typesetting Z specifications.
- czt - Standalone CZT library (classic distribution).
- maven - Instructions how to use CZT libraries deployed to Maven Central.
- CZT Z/Eves- Z Eclipse automated theorem prover IDE
- ZTC- Z type checker
- HOL-Z- High Order Logic Z checker - a plug-in for Isabelle/HOL
Overview
Alloy
Alloy = logic + language + analysis, where
- logic = first order logic + relational calculus
- language = syntax for structuring specifications in the logic
- analysis = bounded exhaustive search for counterexample to a claimed property using SAT
Focused on software engineering
- Alloy- MIT website, from Daniel Jackson
- Alloytools - for describing structures and a tool for exploring them. It has been used in a wide range of applications from finding holes in security mechanisms to designing telephone switching networks
Proof assistants
Isabelle (Cambridge/Muenchen)
- Isabelle- generic proof assistant, allows mathematical formulas to be expressed in a formal language and provides tools for proving those formulas in a logical calculus, originally developed at the University of Cambridge and Technische Universität Muenchen
- Isabelle- University of Cambridge website
- Isabelle- Concrete Semantics (how to)
Coq (INRIA)
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.
- Coq-
- Coq implements a program specification and mathematical higher-level language called Gallina, based on a formal language called the Calculus of Inductive Constructions that itself combines both a higher-order logic and a richly-typed functional programming language
Finite State Machines
- FSM - Wikipedia
- NuSMV- Nex Symbolic Model Checker - open source SAT solver for Temporal Logic such as LTL and CTL - a reimplementation and extension of SMV symbolic model checker
Proposition logic, SAT, SMT
In mathematical logic, satisfiability and validity are elementary concepts of semantics.
- A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true.
- A formula is valid if all interpretations make the formula true.
SAT
SAT refers to the propositional (or boolean) satisfiability problem.
- Satisfiability.org- conference on propositional satisfiability problem (SAT)
- Satlib- benchmark problems, solvers and tools for SAT research
SMT
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.
- By being theory-specific and restricting their language to certain classes of formulas
(such as, typically but not exclusively, quantifier-free formulas), these specialized methods can be implemented in solvers that are more efficient
in practice than general-purpose theorem provers.
- An SMT instance is a formula in first-order logic, where some function and predicate symbols have additional interpretations,
and SMT is the problem of determining whether such a formula is satisfiable.
- SMT - Wikipedia
- SMTLIB- the Satisfiability Module Theories library
- Z3- Satisfiability Modulo Theories (SMT) solver by Microsoft
FOL and predicate logic
Basics
Prolog
KIF
- Knowledge Interchange Format - Wikipedia
- Is a computer language designed to enable systems to share and re-use information from knowledge-based systems.
- Similar to frame languages such as KL-One and LOOM but unlike such language its primary role is not intended as a framework for the expression or use of knowledge but rather for the interchange of knowledge between systems.
Has a declarative semantics.Knowledge can be described as objects, functions, relations, and rules.
- It is a formal language, i.e., it can express arbitrary statements in first order logic and can support reasoners that can prove the consistency of a set of KIF statements.
- KIF also supports non-monotonic reasoning.
- Although the original KIF group intended to submit to a formal standards body, that did not occur. A later version called Common Logic has since been developed for submission to ISO and has been approved and published.
- A variant called SUO-KIF is the language in which the Suggested Upper Merged Ontology SUMO) is written.
Subjective logic
Deontic logic
Other
Number theory
Primes
Graphs
Intro
Graph in ZK
DSP - FFT - wavelets - compression
Matrices
Refer to LTK-SageMath.
- regex - a regular expression is a sequence of characters that define a search pattern
- A regex processor translates a regular expression into an internal representation which can be executed
and matched against a string representing the text being searched in.
- Each character in a regular expression is either a metacharacter or a regular character
that has a literal meaning.
For example, in the regex a., a is a literal character which matches just 'a', while '.' is a metacharacter
that matches every character except a newline.
- Basics:
- a matches letter 'a'
- [a-z] matches all lower case letters from 'a' to 'z'
- '.' is a metacharacter that matches every character except a newline
- a vertical bar separates alternatives ('or'), e.g. gr(a|e)y
- Quantifiers: a quantifier after a token (such as a character) or group specifies how often that a preceding element is allowed to occur
- ? indicates zero or one occurrences of the preceding element. For example, colou?r matches both "color" and "colour".
- * indicates zero or more occurrences of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.
- + indicates one or more occurrences of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac"
- {n} means the preceding item is matched exactly n times.
- Anchors:
- ^The matches any string that starts with The
- end$ matches a string that ends with end
- ^The end$ exact string match (starts and ends with The end)
- roar matches any string that has the text roar in it
- Character classes:
- \d matches a single character that is a digit
- \w matches a word character (alphanumeric character plus underscore)
- \s matches a whitespace character (includes tabs and line breaks)
- \d, \w and \s also present their negations with \D, \W and \S respectively,
for example, \D will perform the inverse match with respect to that obtained with \d,
so \D matches a single non-digit character
- . matches any character as a wildcard, for example, a.b matches any string that contains an "a",
then any other character and then a "b",
a.*b matches any string that contains an "a" and a "b" at some later point.
- Escaping: in order to be taken literally, you must escape the characters ^.[$()|*+?{\with a backslash \
as they have special meaning, e.g. \$\d matches a string that has a $ before one digit
- Non-printables: you can match also non-printable characters like tabs \t, new-lines \n, carriage returns \r
- Using \1 to keep part of the pattern: "[a-z][a-z]" will match any two lower case letters.
If you wanted to search for lines that had two adjoining identical letters, this pattern wouldn't help.
You need to remember what you found, and see if the same pattern occurred again.
- To mark part of a pattern using "\(" and "\)",
- To recall the remembered pattern use "\" followed by a single digit.
Therefore, to search for two identical letters, use "\([a-z]\)\1". You can have 9 different remembered patterns.
- Standards: the IEEE POSIX standard has 3 sets of compliance: BRE (Basic Regular Expressions), ERE (Extended Regular Expressions), and SRE (Simple Regular Expressions) - deprecated
- Regex can be used e.g. in grep or sed, such as 'sed 's/regexp/replacement/g' inputFileName > outputFileName'
- In sed the s stands for substitute, while the g stands for global, which means that all matching occurrences in the line would be replaced.
- The replacement can be literal text or a format string containing the characters & for "entire match" or the special escape sequences \1 through \9 for the nth saved sub-expression
- Regex editor e.g. any https corresponds to /[https\:\/\/]/
- sed - gnu.org page
- sed - wikipedia - basic examples
- Usage: sed SCRIPT INPUTFILE...
- Usage for substitution: sed 's/regexp/replacement/g' inputFileName > outputFileName where
- s represents the substitute command
- g represents the global flag, i.e. replace all occurances found, not only the first one (as by default)
- ...
Humour
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.