## Mathematics Faculty Publications

#### Title

A Modular Integer GCD Algorithm

Article

2-1-2005

#### Publication Title

Journal of Algorithms

#### Abstract

This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U-bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (-p/2,p/2) such that b=UV ^-1(mod p) . When the algorithm is executed on a bit common CRCW PRAM with O(n log n log log log n) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/log n) time on the same number of processors.

Research reported here was done primarily at UFRGS - Instituto de Matematica. First author funded by CNPq grant number 301314194-2. Second author partially funded by FAPERGS, grant number 011316.6.

#### DOI

10.1016/j.jalgor.2004.06.006

Postprint

54

2

COinS
{"ft_lang_label":"__label__en","ft_lang_prob":0.7636555,"math_prob":0.76176566,"size":1694,"snap":"2021-43-2021-49","text_gpt3_token_len":444,"char_repetition_ratio":0.095266275,"word_repetition_ratio":0.0,"special_character_ratio":0.2550177,"punctuation_ratio":0.15133531,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96258354,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-22T19:59:50Z\",\"WARC-Record-ID\":\"<urn:uuid:7748729c-8717-43ff-9e82-7c5418c16875>\",\"Content-Length\":\"41364\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:01f8634d-9b16-4dc5-8591-46af6d3a83ec>\",\"WARC-Concurrent-To\":\"<urn:uuid:e167f95f-6d9c-4228-b679-bbbf239b8903>\",\"WARC-IP-Address\":\"13.57.92.51\",\"WARC-Target-URI\":\"https://engagedscholarship.csuohio.edu/scimath_facpub/156/\",\"WARC-Payload-Digest\":\"sha1:3A2KXDJDFTOAQPTW5NSMJW4X7Q4CZ3XT\",\"WARC-Block-Digest\":\"sha1:J4WNMW7HOM7YZBMBXQ5L3RN6JFSBNJBU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585518.54_warc_CC-MAIN-20211022181017-20211022211017-00359.warc.gz\"}"}