کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332590 | 687692 | 2005 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Factoring into coprimes in essentially linear time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Factoring into coprimes in essentially linear time Factoring into coprimes in essentially linear time](/preview/png/10332590.png)
چکیده انگلیسی
Let S be a finite set of positive integers. A “coprime base for S” means a set P of positive integers such that (1) each element of P is coprime to every other element of P and (2) each element of S is a product of powers of elements of P. There is a natural coprime base for S. This paper introduces an algorithm that computes the natural coprime base for S in essentially linear time. The best previous result was a quadratic-time algorithm of Bach, Driscoll, and Shallit. This paper also shows how to factor S into elements of P in essentially linear time. The algorithms use solely multiplication, exact division, gcd, and equality testing, so they apply to any free commutative monoid with fast algorithms for those four operations; for example, given a finite set S of monic polynomials over a finite field, the algorithms factor S into coprimes in essentially linear time. These algorithms can be used as a substitute for prime factorization in many applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 54, Issue 1, January 2005, Pages 1-30
Journal: Journal of Algorithms - Volume 54, Issue 1, January 2005, Pages 1-30
نویسندگان
Daniel J. Bernstein,