TY - JOUR
T1 - GCD of random linear combinations
AU - Von Zur Gathen, Joachim
AU - Shparlinski, Igor E.
PY - 2006/9
Y1 - 2006/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33747891212&partnerID=8YFLogxK
U2 - 10.1007/s00453-006-0072-1
DO - 10.1007/s00453-006-0072-1
M3 - Article
AN - SCOPUS:33747891212
SN - 0178-4617
VL - 46
SP - 137
EP - 148
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 1
ER -