On the parallel generation of the residues for the continued fraction factoring algorithm

Abstract

In order to implement the continued fraction algorithm on a highly parallel computer, like the Massively Parallel Processor, it is necessary to be able to compute certain numbers which occur at widely-spaced intervals within the continued fraction expansion of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartRoot upper N EndRoot"> <mml:semantics> <mml:msqrt> <mml:mi>N</mml:mi> </mml:msqrt> <mml:annotation encoding="application/x-tex">\sqrt N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. where <italic>N</italic> is the number to be factored. In this paper several properties of the continued fraction expansion of a quadratic irrational are developed. These results are then applied to the development of a very simple algorithm for finding the widely-spaced numbers referred to above.