Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

I've been reading up on ways of factorising numbers through the congruence of squares method (http://en.wikipedia.org/wiki/Congruence_of_squares), and at the moment I'm looking at the continued fraction method, whereby you use the convergents of a continued fraction expansion of Sqrt(N) in order to find a congruence of squares modulo N: I think www.math.dartmouth.edu/~carlp/PDF/implementation.pdf section 2 has one of the few good descriptions of the process I can find online.

However, what I'm struggling to actually see is what the actual advantage of using these convergents is - what do we gain from using the convergents, does it somehow make it easier to find the congruence of squares? Does it typically make it easier to find B-smooth numbers congruent to a square for some small set of primes B, for example? I can see the method is closely related to Dixon's method (http://en.wikipedia.org/wiki/Dixon's_factorization_method), but as I said I fail to see why the CFRAC method is actually advantageous - does it perhaps typically find that the A_{n}^{2}(using the terminology of the linked CFRAC explanation) are congruent to a very small number, in which case more likely to factorise under a set of small primes? Or is it less likely to lead to a trivial factorisation, maybe?

I'd really appreciate any enlightenment - I didn't put this in the homework section because it isn't any set work and I have no specific questions to solve on the issue, I'm just trying to get my head around it, so sorry if it's in the wrong place :) Thankyou very much in advance! --Mathmos6

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Purpose of the Continued Fraction Factorisation Method

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Purpose Continued Fraction | Date |
---|---|

Discrete or continuous spectrum? | Mar 15, 2013 |

What does this answer mean? (continuous functions) | Feb 24, 2013 |

Is it possible to define a basis for the space of continuous functions? | Oct 5, 2012 |

Continued fraction convergents | Oct 29, 2011 |

What is the purpose of the transpose? | Oct 5, 2008 |

**Physics Forums - The Fusion of Science and Community**