GCD of random linear combinations

Joachim Von Zur Gathen*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

We show that for arbitrary positive integers a1, . . ., a m with probability 6/π2 + o(1), the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with gcd(a1, . . ., am). This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability 6/π2 + o(1), via just one gcd of two numbers with about the same size as the initial data (namely the above linear combinations). This algorithm can be repeated to achieve any desired confidence level.

Original languageEnglish
Pages (from-to)137-148
Number of pages12
JournalAlgorithmica (New York)
Volume46
Issue number1
DOIs
Publication statusPublished - Sep 2006

Fingerprint

Dive into the research topics of 'GCD of random linear combinations'. Together they form a unique fingerprint.

Cite this