Methods of extracting root with the residues from multi-bit numbers to meet the challenges of asymmetric cryptography - Винничук, Степан Дмитриевич; Корнейко, Александр Васильевич; Максименко, Евгений Васильевич (Ukrainian Information Security Research Journal, 2016)
Currently asymptotically the fastest factorization methods of multi-bit sequences are methods based on the fundamental ratios of Fermat algorithm. One of the most complex operations in the factorization method of Fermat is a procedure of extracting the square root. Existing methods of extracting the roots are refer to the number of iterative and require the implementation the quite large number the most complex arithmetic operations of multiplication and division. This in turn significantly affects on their temporal assessment. One of the ways of improving the productivity of existing methods for extracting the square root would be using a direct calculation of root without using operations of multiplication or division large numbers. Offered a new method for calculating the square root without using multiplication and division large numbers, which is a modification of the method of extracting roots "in the column." Made a comparative analysis of the described modified method "in a column" with the existing diagonal method (method of Tereshchenko). Offered to use this method in the procedures for analysis of asymmetric cryptographic algorithms