ABSTRACT

Roots and powers In this Appendix we describe two algorithms required for the implementation of the factorization algorithms and primality tests presented in this book. The algo­ rithm of section 1 computes the integer part of the square root of a given positive integer; the algorithm of section 2 computes powers in modular arithmetic.