KARATSUBA BASED MULTIPLIER AND METHOD

摘要

A method of multiplying large integers is disclosed. Two large numbers, x and y, are provided, values are determined in accordance with the Karatsuba multiplication process based on x and y. A first and second value according to the Karatsuba multiplication method are also determined. The third value for use in accordance with the Karatsuba multiplication method is determined by determining C' = (x<SUB>1</SUB>+x<SUB>2</SUB>)[m-l:0]*(y<SUB>1</SUB>,+y<SUB>2</SUB>)[m-l:0] and determining C = C' + ((y<SUB>1</SUB>,+y<SUB>2</SUB>)[2m:2m] AND (x<SUB>1</SUB>+x<SUB>2</SUB>)[m-l:0] + (x<SUB>1</SUB>+x<SUB>2</SUB>)[2m:2m] AND (y<SUB>1</SUB>+y<SUB>2</SUB>)[m:0]) « m, where « is a bitwise shift operation, wherein AND is performed by performing a Boolean AND of a single bit within a first operand with each bit within a second operand and wherein D[j:k] refers to the jth to kth bits of D.