Continued Fraction Algorithm

Raman · 2009-02-25, 11:38

I am not understanding any algorithm.

In the beginning, people in the forum used up so to write:

Quote:

If you want help in understanding an algorithm, I will be more than happy to answer any questions.

Now, I see that people are reluctant to help. I assume that people are getting irritated due to repeated demands.

Quote:

Enough clues??????

I think that it is better for me to behave in a way that I think is good, let whatever happen, I am not going to care.

Take the continued fraction expansion of $\sqrt {kN}$
$\LARGE \sqrt {kN} = q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \frac{1}{q_3 + \frac{1}{\ddots\,}}}}$

In my method, to calculate the value of q_i's that I used up so
$A_{-2}=0$ $A_{-1}=1$ $A_0=\lfloor{\sqrt{kN}}\rfloor$
$B_{-2}=1$ $B_{-1}=0$ $B_0=1$
$A_i=q_iA_{i-1}+A_{i-2}$
$B_i=q_iB_{i-1}+B_{i-2}$
The i^th convergents are given up so by
$\frac{A_i}{B_i}$
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
$\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} \le \lfloor{\sqrt{kN}}\rfloor$
If i is odd, q_i is the least value such that
$\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} > \lfloor{\sqrt{kN}}\rfloor$
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:
$\LARGE \pi = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \frac{1}{\ddots\,}}}}}$

$C_0 = \lfloor \pi \rfloor = 3$
$C_1 = \lfloor \frac{1}{\pi - 3} \rfloor = 7$
$C_2 = \lfloor \frac{1}{\frac{1}{\pi - 3} - 7} \rfloor = 15$
and so on...

But, in the paper by Morrison and Brillhart,
A method of factoring and the factorization of F₇

It is rather given some new formulas, where
$g=\lfloor{\sqrt{kN}}\rfloor$
$g+P_n=q_nQ_n+r_n$ , $0 \le r_n < Q_n$
$g+P_{n+1}=2g-r_n$
$Q_{n+1}=Q_{n-1}+q_n(r_n-r_{n-1})$
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
$q_n = \lfloor \frac{\sqrt{kN}+P_n}{Q_n} \rfloor$
What is P_n?
The term Q_n is indeed OK for me, up so thus.
$A_{n-1}^2 - kNB_{n-1}^2 = (-1)^nQ_n$ .

How come
$0 \le P_n < \sqrt{kN}$
and then
$0 < Q_n < 2 \sqrt{kN}$
thus?

R.D. Silverman · 2009-02-25, 12:05

Quote:

Originally Posted by Raman

I am not understanding any algorithm.

In the beginning, people in the forum used up so to write:
Now, I see that people are reluctant to help. I assume that people are getting irritated due to repeated demands.
I think that it is better for me to behave in a way that I think is good, let whatever happen, I am not going to care.

Take the continued fraction expansion of $\sqrt {kN}$
$\LARGE \sqrt {kN} = q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \frac{1}{q_3 + \frac{1}{\ddots\,}}}}$

In my method, to calculate the value of q_i's that I used up so
$A_{-2}=0$ $A_{-1}=1$ $A_0=\lfloor{\sqrt{kN}}\rfloor$
$B_{-2}=1$ $B_{-1}=0$ $B_0=1$
$A_i=q_iA_{i-1}+A_{i-2}$
$B_i=q_iB_{i-1}+B_{i-2}$
The i^th convergents are given up so by
$\frac{A_i}{B_i}$
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
$\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} \le \lfloor{\sqrt{kN}}\rfloor$
If i is odd, q_i is the least value such that
$\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} > \lfloor{\sqrt{kN}}\rfloor$
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:
$\LARGE \pi = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \frac{1}{\ddots\,}}}}}$

$C_0 = \lfloor \pi \rfloor = 3$
$C_1 = \lfloor \frac{1}{\pi - 3} \rfloor = 7$
$C_2 = \lfloor \frac{1}{\frac{1}{\pi - 3} - 7} \rfloor = 15$
and so on...

But, in the paper by Morrison and Brillhart,
A method of factoring and the factorization of F₇

It is rather given some new formulas, where
$g=\lfloor{\sqrt{kN}}\rfloor$
$g+P_n=q_nQ_n+r_n$ , $0 \le r_n < Q_n$
$g+P_{n+1}=2g-r_n$
$Q_{n+1}=Q_{n-1}+q_n(r_n-r_{n-1})$
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
$q_n = \lfloor \frac{\sqrt{kN}+P_n}{Q_n} \rfloor$
What is P_n?
The term Q_n is indeed OK for me, up so thus.
$A_{n-1}^2 - kNB_{n-1}^2 = (-1)^nQ_n$ .

How come
$0 \le P_n < \sqrt{kN}$
and then
$0 < Q_n < 2 \sqrt{kN}$
thus?

See either Riesel's book, or Knuth Vol 2.

Raman · 2009-02-26, 14:11

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 $Q^2\ (mod\ N)$ , which by using square root, $Q$ 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 $Q_i$ , that is examined, the square root is computed as follows, where $\overline{Q}$ is the value of the least positive remainder of $Q\ (mod\ N)$ .

$i=2,\ \overline{Q}=1,\ R=Q_1$
$X=GCD(R,\ Q_i)$
$\overline{Q}=X\overline{Q}\ (mod\ N)$
$R=\left( \frac{R}{X} \right) \left( \frac{Q_i}{X} \right)$
$i=i+1$
$If\ i \le s\ Then\ Goto\ 2$
$X=\sqrt R$
$\overline{Q}=X\overline{Q}\ (mod\ N)$

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:

One method of calculating g is the following modification of the Newton Raphson recursion: When an initial estimate $x_0 > \sqrt{kN}$ (which can be calculated by using the leading point of kN), successively compute $x_{n+1} = \lfloor \frac{(x_n^2+kN)}{2x_n} \rfloor$ for $n \ge 0$ , where the bracket denotes the greatest integer function. When $x_{n+1} - x_n \ge 0$ , then $g=x_{n+1}$ .

How is the initial estimate $x_0$ being computed so from $\sqrt{kN}$ ? Thus, please explain clearly.

fivemack · 2009-02-26, 14:58

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 FFT-based 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.

Raman · 2009-02-27, 16:42

Finally, is the factoring of the different $Q_n$ values for the continued fraction algorithm only by trial division? Of course, we have that for a prime p to be a factor of $Q_n$ , then p should satisfy the Legendre Symbol $\left( \frac{kN}{p} \right)$ = 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 $Q_n$ values for this algorithm?

For the Quadratic Sieve algorithm, we have that if a prime p divides $x^2-kN$ , then $x^2=kN\ (mod\ p)$ , hence we need to check for the prime factor p for only those values of x, that which are congruent to the value of
$x \equiv \sqrt{kN}\ (mod\ p)$

Anything else that is like that case for this continued fraction factoring algorithm? Of course, for the optimizations, for ever.

jasonp · 2009-02-27, 16:59

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.

Raman · 2009-02-27, 17:48

The question is how to recognize those primes that do not divide the value of $Q_n$ for any value of n that is being given up.
Besides the fact that we can skip up those primes for which $\left( \frac{kN}{p} \right)$ = -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
$x \equiv \pm \sqrt{kN} \ (mod\ p)$ .

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 $A_{n-1}$ here,
are produced at random, from the continued fraction expansion of $\sqrt{kN}$ , by using this method.

We have the fact that, this congruence is being satisfied up always
$A_{n-1}^2 = (-1)^nQ_n\ (mod\ N)$

Quote:

90% of the time is being spent in 10% of the code. The program spends majority of its execution time within the loops. Likewise, for these class of the algorithms, the program spends the majority of the time for sieving and then factoring the values of the $Q_n$ , of course, for ever.

jasonp · 2009-02-27, 18:01

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 40-digit 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)

2009-02-27, 16:42	#5
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts	Finally, is the factoring of the different $Q_n$ values for the continued fraction algorithm only by trial division? Of course, we have that for a prime p to be a factor of $Q_n$ , then p should satisfy the Legendre Symbol $\left( \frac{kN}{p} \right)$ = 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 $Q_n$ values for this algorithm? For the Quadratic Sieve algorithm, we have that if a prime p divides $x^2-kN$ , then $x^2=kN\ (mod\ p)$ , hence we need to check for the prime factor p for only those values of x, that which are congruent to the value of $x \equiv \sqrt{kN}\ (mod\ p)$ 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 2009-02-27 at 16:45

2009-02-27, 18:01	#8
jasonp Tribal Bullet Oct 2004 2·3·19·31 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 40-digit 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 2009-02-27 at 18:02

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	2013-11-29 21:43
An Egyptian Fraction	Yamato	Puzzles	8	2013-05-16 15:50
TF algorithm(s)	davieddy	Miscellaneous Math	61	2011-07-06 20:13
Partial fraction of this expression?please!!	tinhnho	Miscellaneous Math	4	2005-01-17 19:45
Continued Fraction of Primes	Cyclamen Persicum	Miscellaneous Math	9	2003-04-13 14:56

2009-02-26, 14:58	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×3,191 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.2710^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 FFT-based 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.

2009-02-27, 16:59	#6
jasonp Tribal Bullet Oct 2004 2×3×19×31 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.