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

Proposed Research

My primary goal is to obtain an analysis of the average case runtime. However, in order to obtain this, I will need some preliminary results.

First, I intend to investigate more fully the conditions for which the sequence of pseudo-squares and residues will provide a factorization. A set of numbers that I can prove this algorithm does not work on would be extremely valuable for security purposes. Second, I intend to investigate the connection with quadratic forms more fully. Although Shanks assumed it to be true and probably had a proof, I have not yet seen a formal proof that the composition of two quadratic forms is another quadratic form in the same continued fraction expansion, an especially interesting fact considering the usual necessity of reducing the result. Third, I intend to investigate the conjecture that the test of direction is accurate. If it were possible to prove these, the proofs would provide valuable information for assessing the algorithm as it currently stands, provide valuable insight into possible improvements, and provide a base of information about continued fractions that someone else could build on later.

Second, I intend to analyze the ability to perform a test of direction, specifically whether the frequency changes with larger choices of $N$ and how the time required for this test changes. This combined with proofs or at least good arguments for the other conjectures will provide for an analysis of average runtime. This will determine how serious of a threat it poses to the RSA system. I intend to use C++ both to research the algorithm and to produce a working implementation of the algorithm.


next up previous contents
Next: Proposed Timeline Up: PROPOSED METHOD OF INVESTIGATION Previous: Current Research   Contents
David Joyner 2004-02-23