TY - JOUR
T1 - GCD of random linear forms
AU - Von Gathen, Joachim Zur
AU - Shparlinski, Igor E.
PY - 2004
Y1 - 2004
N2 - We show that for arbitrary positive integers a1,.,., a m, with probability at least 6/π2 + o(l), the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with gcd(a1,.,.,om). This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability at least 6/π2 + o(l), via just one gcd of two numbers with about the same size as the initial data (namely the above linear combinations). Naturally, this algorithm can be repeated to achieve any desired confidence level.
AB - We show that for arbitrary positive integers a1,.,., a m, with probability at least 6/π2 + o(l), the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with gcd(a1,.,.,om). This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability at least 6/π2 + o(l), via just one gcd of two numbers with about the same size as the initial data (namely the above linear combinations). Naturally, this algorithm can be repeated to achieve any desired confidence level.
UR - http://www.scopus.com/inward/record.url?scp=35048891554&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:35048891554
SN - 0302-9743
VL - 3341
SP - 464
EP - 469
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -