In this project we describe novel methods of watermarking data using quadratic residues and random numbers. The new methods are fast, generic and improve the security of the watermark in most known watermarking techniques. The basic idea is illustrated first for the simple case of watermarking numerical data by encrypting the message into the low order bits of floating point numbers. These numbers, interpreted as integers, are modified slightly to force them to be quadratic residues or nonresidues modulo a secret prime, according to the next bit of the watermark message. Because of the nearly uniform distribution of quadratic residues and nonresidues, usually little change in the number is needed. By adding a simple random number generator and changing the way the watermark bit is encoded, we get an algorithm which damages at most one bit of each number. In this situation, the original data is not needed to read the watermark, even if the data is truncated. Only the secret prime is needed to read it. We explain how the methods can be applied to improve any watermarking technique in which the watermark is inserted into a list of numbers one bit per number.