Rapid and reliable test of SOCs necessitates upfront consideration of the test power issues. Special attention should be paid to scan-based cores as the test power problem is more severe due to excessive switching activity stemming from scan chain transitions during shift operations. We propose a scan chain modification methodology that transforms the stimuli to be inserted to the scan chain through logic gate insertion between scan cells, reducing scan chain transitions. We provide a mathematical analysis that helps model the impact of scan chain modifications on test stimuli transformations. Based on this analysis, we develop algorithms for transforming a set of test vectors into power-optimal test stimuli through cost-effective scan chain modifications. Even in the highly challenging case of fully specified test vectors, more than an order of magnitude reduction in scan-in power is attained by the proposed methodology, exceeding previous power reduction levels significantly.