Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $N=pq$, would $\frac{p-1}{2}$ steps be fast compared with extant factoring methods?

share|improve this question
That is precisely as fast as trial division by all odd numbers (provided a single trial division has cost $O(1)$) –  Hagen von Eitzen Feb 17 '13 at 16:12

1 Answer 1

See for example Wikipedia, where sub-exponential methods are discussed (note that this is measured in terms of the bits needed to represent $N$, not of $N$ itself).

share|improve this answer
thanks for the response. I see that now. –  ratking Feb 19 '13 at 22:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.