Mathmos6
Sep27-10, 03:27 PM
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%27s_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
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%27s_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