We present a procedural method for synthesizing large textures from an input texture sample. The basis of our algorithm is the chaos mosaic, a technique for synthesizing textures with an even and visually stochastic distribution of the local features of the input sample. The chaos mosaic is fast. For synthesizing textures of the same size and comparable quality, our algorithm is orders of magnitude faster than existing algorithms. On a PC we can synthesize a 512 X 512 texture from a 64 X 64 sample in just 0.03 seconds. More importantly, the chaos mosaic facilitates memory efficient texture rendering through procedural texturing. Like traditional solid texture techniques, the chaos mosaic allows us to synthesize and render synthetic textures that, if stored explicitly as textures, would require prohibitively large amounts of storage. As an example, we demonstrate that an 100k X 100k synthetic texture can be interactively visualized on a modest PC without suffering from latency. Finally, the chaos mosaic can drastically reduce the bandwidth for interactive 3D graphics delivered across the internet.