mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-02-25, 11:38   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default 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
Raman is offline   Reply With Quote
Old 2009-02-25, 12:05   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-02-26, 14:11   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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
Raman is offline   Reply With Quote
Old 2009-02-26, 14:58   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2009-02-27, 16:42   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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
Raman is offline   Reply With Quote
Old 2009-02-27, 16:59   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-02-27, 17:48   #7
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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
Raman is offline   Reply With Quote
Old 2009-02-27, 18:01   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default

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
jasonp is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 19:49.

Sat Nov 28 19:49:17 UTC 2020 up 79 days, 17 hrs, 3 users, load averages: 1.41, 1.58, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.