Using Lucas sequences to factor large integers near group orders. (Q2735219)

Using Lucas sequences, the author proves two theorems. Theorem 1. There exists an algorithm for finding prime divisors \(p<q\) of \(N\) in \(O(\log^3N+| r| \log^2N )\) bit operations, provided \(N=pq\) with \(q=k(p-1)+r\) and \(| r| <(p-3)/2\). Theorem 2. There exists an algorithm for finding prime divisors \(p<q\) of \(N\) in \(O(\log^3N+| r| \log^2N )\) bit operations, provided \(N=pq\) with \(q=k(p+1)+r\) and \(| r| <(p+1)/2\).