The computational cost of embedding information in a digital representation is reduced by making a set of at least two copies of the digital representation and altering subdivisions of the copies so that corresponding subdivisions in the copies are distinguishable from each other. The subdivisions may be arbitrary or may be functional subdivisions of the digital representation. The subdivisions may be distinguishable by features such as watermarks that do not affect the way in which the digital representation is normally used. The marked copy in which the information is embedded is then made by selecting a given subdivision in the marked copy from one of the set of copies. Selection may be done using a selection string that has an element for each subdivision. The value of the element indicates which of the set of digital representations the subdivision corresponding to the element is to be selected from. The result of this procedure is a sequence of distinguishable subdivisions in the marked copy, and the sequence carries the embedded information. Each marked copy may have a unique sequence, in which case the sequence functions as a fingerprint for the copy. The sequence may also encode information. Examples are an identification of the recipient of the copy, information about the transaction that resulted in the copy being made, or encoded information about the content of the marked copy.