Fast parallel GCD algorithm of many integers

摘要

We present a new parallel algorithm which computes the GCD of n integers of O(n) bits in O(n/ log n) time with O(n~(2+?)) processors, for any ? > 0 on CRCW PRAM model.