20090225, 11:38  #1  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Continued Fraction Algorithm
I am not understanding any algorithm.
In the beginning, people in the forum used up so to write: Quote:
Quote:
Take the continued fraction expansion of In my method, to calculate the value of q_{i}'s that I used up so The i^{th} convergents are given up so by The even convergents are in deficit, and the odd convergents are in excess. So, thus, to calculate the values of q_{i}'s in my trial program, I used up so If i is even, q_{i} is the least value such that If i is odd, q_{i} is the least value such that This is the algorithm that I used up so for my trial program. If it is admissible to use floating point arithmetic, q_{i} can be directly calculated as follows: and so on... But, in the paper by Morrison and Brillhart, A method of factoring and the factorization of F_{7} It is rather given some new formulas, where , I don't understand how these formulas are arrived at g is reduced to an integer, so how the bottom three formulas will produce an indefinite continued fraction expansion? Just for theory, not the implementations at all, by now itself. Of course, for the time being.. How come What is P_{n}? The term Q_{n} is indeed OK for me, up so thus. . How come and then thus? Last fiddled with by Raman on 20090225 at 11:42 

20090225, 12:05  #2  
Nov 2003
2^{6}·113 Posts 
Quote:
See either Riesel's book, or Knuth Vol 2. 

20090226, 14:11  #3  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Once the matrix has been solved, the history matrix contains the rows which contribute to the dependency. The relations are multiplied to get the value of , which by using square root, is resolved.
This is the technique that is being mentioned so, in the paper of Morrison and Brillhart, rather than maintaining a count of each prime power, and then multiplying each prime by half the value of power. For each relation , that is examined, the square root is computed as follows, where is the value of the least positive remainder of . Consider the step 7 now. It is given that if R is sufficiently small, then X can be easily computed by taking its square root. I don't understand this fact. Can someone please explain clearly? If R is greater than N, it will be reduced (mod N). How do we know (by using so the brute force techniques?) what multiple of N should be added up to R, so as to make it a perfect square? It is somewhat pointed to remark 3.4 Quote:
Last fiddled with by Raman on 20090226 at 14:17 

20090226, 14:58  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
6,323 Posts 
The "leading point of kN" is referring to the first few digits of kN (IE, if you know kN is 88 digits long and begins 1.427, so is about 14.27*10^86, a starting estimate for sqrt(kN) would be sqrt(14.27) * 10^43 = 3.77*10^43).
The algorithm you're writing about never tells you to reduce R mod N; you just keep multiplying Qi (which are integers) together until you get an enormous integer, then just take the square root of that integer. But this code was written to run on amazingly slow computers, and before the FFTbased multiply algorithms had reached the state they're in now, so at the time it was impractical to work with such large integers, and they had to invent a cleverer algorithm which is done in the next section of the paper. 
20090227, 16:42  #5 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Finally, is the factoring of the different values for the continued fraction algorithm only by trial division? Of course, we have that for a prime p to be a factor of , then p should satisfy the Legendre Symbol = 0 or 1.
Further, we have that properties of dividing by using brute force techniques only upto the Factor Base primes, and then discarding away those relations, whose cofactor is greater than the Upper Bound. Do we have any other constraints or conditions for the factoring of the various values for this algorithm? For the Quadratic Sieve algorithm, we have that if a prime p divides , then , hence we need to check for the prime factor p for only those values of x, that which are congruent to the value of Anything else that is like that case for this continued fraction factoring algorithm? Of course, for the optimizations, for ever. Last fiddled with by Raman on 20090227 at 16:45 
20090227, 16:59  #6 
Tribal Bullet
Oct 2004
110110100001_{2} Posts 
You can use a factor base that will skip over primes that will never divide the numbers produced at each step, and you can also use single and double large primes on numbers that survive that step, combined with generation of cycles. Put another way, whether you use QS, NFS or CFRAC the postprocessing behaves the same, manipulating graph quantities that are derived from the relations produced by the algorithm.
You can also use Bernstein's batch factoring algorithm to massively speed up trial division by larger primes, or his batch gcd algorithm to flag relations that are likely to be smooth. I'm quite partial to the latter. 
20090227, 17:48  #7  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
The question is how to recognize those primes that do not divide the value of for any value of n that is being given up.
Besides the fact that we can skip up those primes for which = 1 In the Quadratic Sieve factoring algorithm, we need to test those values of x, for a prime p, that satisfies the congruence, for which . It produces two arithmetic progressions, with a common difference of p, for each of the both sequences. Like that, anything existing for the continued fraction factoring algorithm? The values of here, are produced at random, from the continued fraction expansion of , by using this method. We have the fact that, this congruence is being satisfied up always Quote:
Last fiddled with by Raman on 20090227 at 18:00 

20090227, 18:01  #8 
Tribal Bullet
Oct 2004
6641_{8} Posts 
No, there's no way to just look at one of those numbers and immediately know a collection of small primes that does not divide it. This is why CFRAC has so much trouble even with 40digit numbers, and QS completes in milliseconds. Using a sieve in QS improves the asymptotic complexity over CFRAC, as well as the implied constant in the asymptotics (getting both of these is pretty unusual in an advanced algorithm; look at how big a number has to be before NFS becomes faster than QS despite the additional overhead of NFS)
Last fiddled with by jasonp on 20090227 at 18:02 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
why continued fractions gives one factor for N=(4m+3)(4n+3)  wsc811  Miscellaneous Math  6  20131129 21:43 
An Egyptian Fraction  Yamato  Puzzles  8  20130516 15:50 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Partial fraction of this expression?please!!  tinhnho  Miscellaneous Math  4  20050117 19:45 
Continued Fraction of Primes  Cyclamen Persicum  Miscellaneous Math  9  20030413 14:56 