mersenneforum.org > Math Continued Fraction Algorithm
 Register FAQ Search Today's Posts Mark Forums Read

2009-02-25, 11:38   #1
Raman
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:
 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 qi'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 ith 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 qi's in my trial program, I used up so

If i is even, qi 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, qi 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, qi 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 F7

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 Pn?
The term Qn 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?

Last fiddled with by Raman on 2009-02-25 at 11:42

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

Nov 2003

22·5·373 Posts

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 qi'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 ith 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 qi's in my trial program, I used up so If i is even, qi 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, qi 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, qi 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 F7 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 Pn? The term Qn 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.

2009-02-26, 14:11   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

100111010012 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 $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.

Last fiddled with by Raman on 2009-02-26 at 14:17

 2009-02-26, 14:58 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 144648 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 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: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, 16:59 #6 jasonp Tribal Bullet     Oct 2004 DD716 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.
2009-02-27, 17:48   #7
Raman
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 $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.

Last fiddled with by Raman on 2009-02-27 at 18:00

 2009-02-27, 18:01 #8 jasonp Tribal Bullet     Oct 2004 354310 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 wsc811 Miscellaneous Math 6 2013-11-29 21:43 Yamato Puzzles 8 2013-05-16 15:50 davieddy Miscellaneous Math 61 2011-07-06 20:13 tinhnho Miscellaneous Math 4 2005-01-17 19:45 Cyclamen Persicum Miscellaneous Math 9 2003-04-13 14:56

All times are UTC. The time now is 08:20.

Fri Jan 21 08:20:33 UTC 2022 up 182 days, 2:49, 0 users, load averages: 2.02, 1.55, 1.40