View Single Post
Old 2019-02-10, 16:53   #29
Till's Avatar
"Tilman Neumann"
Jan 2016

22·109 Posts

We would like to point out two more things:

1. Fast trial division by "multiplication of the inverse" is essential for the performance of Hart_TDiv_Race. With standard trial division, it would take twice the time, and then Hart_Fast (in the same package as Hart_TDiv_Race) would be much faster for hard semiprimes (Hart_Fast is faster in that case than our Lehman implementation, too).

2. Lehman's and Hart's algorithms seem to be very close relatives. Our "Lehman implementation" spends ~90% of time and finds ~90% of factors in the "Hart loops" ("medium/long range", "long tail"). On the other hand, our "Hart implementation" profits immensely from the congruences derived by Lehman.
Till is offline   Reply With Quote