Præimage

Præimage, or preimage in English, is a term used in mathematics and related fields to describe inputs that map to outputs under a function. If f: A → B is a function and Y is a subset of B, the præimage of Y under f is f^{-1}(Y) = { x ∈ A | f(x) ∈ Y }. For a single element b ∈ B, the præimage is f^{-1}({b}) = { x ∈ A | f(x) = b }, also called the fibre of b. The concept is paired with the image, which is the set f(X) = { f(x) | x ∈ X } for X ⊆ A.

Properties and examples: Preimages always exist for any Y ⊆ B. They respect set operations: f^{-1}(Y ∪ Z) = f^{-1}(Y) ∪ f^{-1}(Z) and f^{-1}(Y ∩ Z) = f^{-1}(Y) ∩ f^{-1}(Z). If f is not injective, a given output can have multiple preimages; if no element of A maps to Y, the preimage is the empty set.

In cryptography, præimage refers to the input that produces a given hash output. A hash function H is said to have preimage resistance if, given a value y, it is computationally infeasible to find any x with H(x) = y. This is distinct from second preimage resistance (finding a different input with the same output) and collision resistance (finding two inputs that yield the same output).

Etymology and usage: The term originates from Latin-based mathematical language and is used in Danish, Norwegian, and related languages as præimage. In English, the standard term is preimage, sometimes written inverse image in older texts. See also image, inverse function, and inverse image.