Computing square root of a large Positive Integer

Abstract

Dealing in large number is of interest in asymmetric key cryptography using RSA. The security of RSA is solely based on difficulty of factorization of a large number. Factoring a number requires finding all divisible primes less than or equal to the square root of the number. Proposed here is a new algorithm to compute the square root of large positive integer. The algorithm is based on the implementation of long division method also known as manual method we usually use to find the square root of a number. To implement the long division method, the given number is first represented in a radix-10 representa and then Bino’s Model of Multiplication is used to systematically implement the long division method. A representa is a special array to represent a number in the form of an array so as to enable us to treat the representas in the same way as we treat numbers. This simplifies the difficulty of dealing large numbers in a computer. The proposed algorithm is applied to the RSA–challenge numbers for factorization. The square roots of the challenge numbers can be computed easily in less than a second. The square roots of first few challenge number and last few challenge number are also provided, which may be used for factorization of corresponding challenge number.

Key words: Asymmetric key cryptogra phy, Bino’s Model of Multiplication, Large number manipulation, Long division method, Prime factorization, RSA challenge numbers, Representa, Square root computation