1. A digital watermark embedding device, comprising: an orthogonal-pattern generating unit configured to generate orthogonal patterns each formed of a combination of elements of −1's and +1's and orthogonal to one another; an embedding-information converting unit configured to convert inputted information to be embedded into a bit string formed of “0's” and “1's”, replace each bit of the bit string with one pattern of the orthogonal patterns, the one pattern being determined by a length of the bit string and a value of the bit, to generate an embedding pattern; and a digital-watermark embedding unit configured to embed the embedding pattern from the embedding-information converting unit in an input image and output an image after embedding, wherein the embedding-information converting unit determines which of the orthogonal patterns is used according to the number of bits of the information to be embedded.