کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10325826 | 677079 | 2012 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characteristic set algorithms for equation solving in finite fields
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Characteristic set algorithms for equation solving in finite fields Characteristic set algorithms for equation solving in finite fields](/preview/png/10325826.png)
چکیده انگلیسی
Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular set is given. An improved zero decomposition algorithm is proposed to reduce the zero set of an equation system to the union of zero sets of monic proper triangular sets. The bitsize complexity of this algorithm is shown to be O(ln) for Boolean polynomials, where n is the number of variables and lâ¥2 is the number of equations. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials occurred during the computation do not exceed the sizes of the input polynomials and the bitsize complexity of algorithm is O(nd) for input polynomials with n variables and degree d. The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations raising from stream ciphers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Symbolic Computation - Volume 47, Issue 6, June 2012, Pages 655-679
Journal: Journal of Symbolic Computation - Volume 47, Issue 6, June 2012, Pages 655-679
نویسندگان
Xiao-Shan Gao, Zhenyu Huang,