Chapter 12. Factoring Methods

Previous Chapter

Next Chapter

This chapter has a detailed discussion of the continued fraction factoring method and the quadratic sieve. To factor a composite number n, the continued fraction method uses the continued fraction expansion of tex2html_wrap_inline250 to generate congruences tex2html_wrap238 . These are combined to produce a congruence of the form tex2html_wrap239 ,and using this, it may possible factor n. The quadratic sieve factors numbers of the form tex2html_wrap240 to generate congruences tex2html_wrap238 , from which a congruence tex2html_wrap239 is obtained.