GCD of random linear forms

Joachim Zur Von Gathen; Igor E. Shparlinski

GCD of random linear forms

Joachim Zur Von Gathen^*, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

We show that for arbitrary positive integers a₁,.,., a _m, with probability at least 6/π² + o(l), the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with gcd(a₁,.,.,o_m). This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability at least 6/π² + 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.

Original language	English
Pages (from-to)	464-469
Number of pages	6
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3341
Publication status	Published - 2004

Cite this

@article{7ffe3b0c3c954262b1863ada7eba1887,

title = "GCD of random linear forms",

abstract = "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.",

author = "{Von Gathen}, {Joachim Zur} and Shparlinski, {Igor E.}",

year = "2004",

language = "English",

volume = "3341",

pages = "464--469",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer, Springer Nature",

}

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

VL - 3341

SP - 464

EP - 469

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

GCD of random linear forms

Abstract

Other files and links

Fingerprint

Cite this