اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
132
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We indicate a strategy in order to construct bilinear multiplication algorithms of type Chudnovsky in large extensions of any finite field. In particular, by using the symmetric version of the generalization of Randriambololona specialized on the elliptic curves, we show that it is possible to construct such algorithms with low bilinear complexity. More precisely, if we only consider the Chudnovsky-type algorithms of type symmetric elliptic, we show that the symmetric bilinear complexity of these algorithms is in $O(n(2q)^{log_q^*(n)})$ where $n$ corresponds to the extension degree, and $log_q^*(n)$ is the iterated logarithm. Moreover, we show that the construction of such algorithms can be done in time polynomial in $n$. Finally, applying this method we present the effective construction, step by step, of such an algorithm of multiplication in the finite field $F_{3^{57}}$.
قيم البحث
اقرأ أيضاً
We propose a Recursive Polynomial Generic Construction (RPGC) of multiplication algorithms in any finite field $mathbb{F}_{q^n}$ based on the method of D.V. and G.V. Chudnovsky specialized on the projective line. They are usual polynomial interpolati
on algorithms in small extensions and the Karatsuba algorithm is seen as a particular case of this construction. Using an explicit family of such algorithms, we show that their bilinear complexity is quasi-linear with respect to the extension degree n, and we give a uniform bound for this complexity. We also prove that the construction of these algorithms is deterministic and can be done in polynomial time. We give an asymptotic bound for the complexity of their construction.
The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear whith respect to the degree of the extension. Recently, Randriambololona has generalized the method
, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. We describe the effective algorithm of this asymmetric method, without derivated evaluation. Finally, we give examples with the finite field $F_{16^{13}}$ using only rational places, $F_{4^{13}}$ using also places of degree two and $F_{2^{13}}$ using also places of degree four.
We propose several constructions for the original multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve its scalar complexity. We highlight the set of generic strategies who underlay the optimization of the scalar complexity, accor
ding to parameterizable criteria. As an example, we apply this analysis to the construction of type elliptic Chudnovsky$^2$ multiplication algorithms for small extensions. As a case study, we significantly improve the Baum-Shokrollahi construction for multiplication in $mathbb F_{256}/mathbb F_4$.
Thanks to a new construction of the so-called Chudnovsky-Chudnovsky multiplication algorithm, we design efficient algorithms for both the exponentiation and the multiplication in finite fields. They are tailored to hardware implementation and they al
low computations to be parallelized while maintaining a low number of bilinear multiplications. We give an example with the finite field ${mathbb F}_{16^{13}}$.
We give non-torsion counterexamples against the integral Tate conjecture for finite fields. We extend the result due to Pirutka and Yagita for prime numbers 2,3,5 to all prime numbers.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
