next up previous contents
Next: Glossary Up: PROPOSED METHOD OF INVESTIGATION Previous: Proposed Research   Contents

Proposed Timeline

February 2004 - April 2004

I will investigate the conditions for which this algorithm provides a factorization. In Theorem 2, I have already proved that the algorithm works for a significant number of integers6, but I still need to research more fully what integers it does and does not work on and a more thorough explanation of why. I will continue researching the work done by Daniel Shanks, specifically attempting to obtain a copy of an incomplete paper in which he describes SQUFOF in more detail [W], hopefully explaining in some detail where he originally got his idea and why it works. This should provide some light into the rest of the project.

May 2004 - July 2004

I will investigate the connection between quadratic forms and continued fractions. I will begin by seeking for some characteristic of a quadratic form that distinguishes the continued fraction that it occurs in. In addition to providing a formal proof that a binary search is possible, this research is likely to also shed some light on the test of direction itself.

August 2004 - October 2004

I will investigate the conjecture that the first part of the test of direction is accurate, the relatively simple case when the condition $Q_i\vert Q_{i-1}$ is met. I will first search for counterexamples. If I am able to find any, I will analyze what goes wrong. From this, I will modify the conditions if necessary. I will also investigate the connection back to SQUFOF. Either way, I believe that a proof by induction on $i$, the index of the pseudo-squares, should be possible. In mid October, I will begin work on the mid-term report in order to finish it by the beginning of December.

November 2004 - December 2004

I will investigate the second part of the test of direction, the case when a multiple $k$ is used and the condition that $Q_{i+3}\vert Q'_1$ is met. I will first analyze to what extent $Q_{i+5}$ and $Q_{i+7}$ relate similarly. This will either provide an insight into how $Q_{i+3}$ is distinct or how the entire sequence may be related to the original sequence. I will attempt a proof, but I believe that in the process of developing a proof, I will discover that it is possible to achieve this test some other way.

In December, I will finish the mid-term report and begin working on the final write-up.

January 2005 - February 2005

I will analyze the frequency with which a test of direction may be performed. At this point, it is possible that the approach to testing direction may be entirely changed by discoveries through the earlier proofs. However, regardless of how the test is done, I will first use significant computer time conducting this analysis. From this, I will analyze which numbers have a higher or lower frequency and attempt to understand the variations. Also, I will attempt to understand the characteristics of pseudo-squares that do provide for a test of direction. With this understanding, I should be able to produce proof of this frequency, which will then provide a complete analysis of runtime.

I will continue inserting this information into my final write-up.

March 2005 - May 2005

I will complete the final write-up for the Trident Scholar Committee and produce a running computer implementation of the algorithm.


next up previous contents
Next: Glossary Up: PROPOSED METHOD OF INVESTIGATION Previous: Proposed Research   Contents
David Joyner, wdj@usna.edu, 2004-02-23