Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Purpose of the Continued Fraction Factorisation Method

  1. Sep 27, 2010 #1
    Hi all,

    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 An2 (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
     
    Last edited by a moderator: Apr 25, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted