Polylog depth circuits for integer factoring and discrete logarithms (Q1322462): Difference between revisions

In order to find a factor of a given integer \(N\), \textit{J. D. Dixon} [Math. Comput. 36, 255-260 (1981; Zbl 0452.10010)] chose an integer \(B\), and then randomly chose integers from \([2, N-1]\) until a sufficient number, for which all the prime factors of \(r^ 2\pmod N\) are less than \(B\), have been found. This leads to integers \(x\), \(y\) such that \(x^ 2\equiv y^ 2\pmod N\), whence a factor of \(N\) is found, provided that \(x\not\equiv \pm y\pmod N\). In the present paper the author uses a much smaller value of \(B\) than Dixon did, but also uses parallel processing extensively. By finding enough factors of \(N\) the complete factorization of \(N\) is found with probability \(1-o(1)\) using circuits of depth \(O(\log^{2d+2} n)\) and size \(O(n/ \log^ d n)\), where \(d\) is a positive constant, and \(n\) is the length of the input. The same ideas are applied to finding discrete logarithms in the finite field \(\text{GF}(p)\), where \(p\) is prime. There is a discussion of possible improvements in the method, and its extension to fields of intermediate size characteristic.