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.