Matching Modulo Divisors, and a Simple N^1/4 Factoring Algorithm

Eric Bach

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-84-187

, 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-187.pdf

We present an algorithm for the following problem: given x(1),...,x(m), distinct modulo N, find two numbers in the list that are congruent modulo a proper divisor of N. The number of steps required is less than m times a polynomial in logN. This gives a simple proof that N can be factored in expected time O(N^(1/4+e)) for any e>0.

BibTeX citation:

@techreport{Bach:CSD-84-187,
    Author= {Bach, Eric},
    Title= {Matching Modulo Divisors, and a Simple N^1/4 Factoring Algorithm},
    Year= {1984},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5972.html},
    Number= {UCB/CSD-84-187},
    Abstract= {We present an algorithm for the following problem: given <i>x(1)</i>,...,<i>x(m)</i>, distinct modulo <i>N</i>, find two numbers in the list that are congruent modulo a proper divisor of <i>N</i>.  The number of steps required is less than <i>m</i> times a polynomial in log<i>N</i>.  This gives a simple proof that <i>N</i> can be factored in expected time <i>O</i>(<i>N</i>^(1/4+<i>e</i>)) for any <i>e</i>>0.},
}

EndNote citation:

%0 Report
%A Bach, Eric 
%T Matching Modulo Divisors, and a Simple N^1/4 Factoring Algorithm
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-187
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5972.html
%F Bach:CSD-84-187