In this paper, a novel data hiding technique is proposed, as an improvement over the Fibonacci LSB data-hiding technique proposed by Battisti et al. [1]. First we mathematically model and generalize our approach. Then we propose our novel technique, based on decomposition of a number (pixel-value) in sum of prime numbers. The particular representation generates a different set of (virtual) bit-planes altogether, suitable for embedding purposes. They not only allow one to embed secret message in higher bit-planes but also do it without much distortion, with a much better stego-image quality, and in a reliable and secured manner, guaranteeing efficient retrieval of secret message. A comparative performance study between the classical Least Significant Bit (LSB) method, the Fibonacci LSB data-hiding technique and our proposed schemes has been done. Analysis indicates that image quality of the stego-image hidden by the technique using Fibonacci decomposition improves against that using simple LSB substitution method, while the same using the prime decomposition method improves drastically against that using Fibonacci decomposition technique. Experimental results show that, the stego-image is visually indistinguishable from the original cover-image.