اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
257
0
0.0
(
0
)
تأليف
Antoine Joux
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered independently by several groups is to use this representation as a starting point for small characteristic finite field discrete logarithm algorithms. This idea has been recently proposed by two groups working on it, in order to achieve provable quasi-polynomial time for discrete logarithms in small characteristic finite fields. In this paper, we dont try to achieve a provable algorithm but, instead, investigate the practicality of heuristic algorithms based on elliptic bases. Our key idea, is to use a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms. We havent performed any record computation with this new method but our experiments with the field F 3 1345 indicate that switching to elliptic representations might be possible with performances comparable to the current best practical methods.
قيم البحث
اقرأ أيضاً
This paper proposes a new signature scheme based on two hard problems : the cube root extraction modulo a composite moduli (which is equivalent to the factorisation of the moduli, IFP) and the discrete logarithm problem(DLP). By combining these two c
ryptographic assumptions, we introduce an efficient and strongly secure signature scheme. We show that if an adversary can break the new scheme with an algorithm $mathcal{A},$ then $mathcal{A}$ can be used to sove both the DLP and the IFP. The key generation is a simple operation based on the discrete logarithm modulo a composite moduli. The signature phase is based both on the cube root computation and the DLP. These operations are computationally efficient.
Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Mo
dule-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for neater and faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversarys benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor may be utilised in order to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an easy instance of SVP. However, it is important to note that this work does not break Ring-LWE or Module-LWE, since the security reduction is from worst case ideal or module SVP to average case Ring-LWE or Module-LWE respectively, and is one way.
We study different aspects of quantum field theory at finite density using methods from quantum information theory. For simplicity we focus on massive Dirac fermions with nonzero chemical potential, and work in $1+1$ space-time dimensions. Using the
entanglement entropy on an interval, we construct an entropic $c$-function that is finite. Unlike what happens in Lorentz-invariant theories, this $c$-function exhibits a strong violation of monotonicity; it also encodes the creation of long-range entanglement from the Fermi surface. Motivated by previous works on lattice models, we next calculate numerically the Renyi entropies and find Friedel-type oscillations; these are understood in terms of a defect operator product expansion. Furthermore, we consider the mutual information as a measure of correlation functions between different regions. Using a long-distance expansion previously developed by Cardy, we argue that the mutual information detects Fermi surface correlations already at leading order in the expansion. We also analyze the relative entropy and its Renyi generalizations in order to distinguish states with different charge and/or mass. In particular, we show that states in different superselection sectors give rise to a super-extensive behavior in the relative entropy. Finally, we discuss possible extensions to interacting theories, and argue for the relevance of some of these measures for probing non-Fermi liquids.
We recast elliptic surfaces over the projective line in terms of the non-commutative tori with real multiplication. The correspondence is used to study the Picard numbers, the ranks and the minimal models of such surfaces. As an example, we calculate
the Picard numbers of elliptic surfaces with complex multiplication.
We study compactifications of Drinfeld half-spaces over a finite field. In particular, we construct a purely inseparable endomorphism of Drinfelds half-space $Omega (V)$ over a finite field $k$ that does not extend to an endomorphism of the projectiv
e space $P (V)$. This should be compared with theorem of Remy, Thuillier and Werner that every $k$-automorphism of $Omega (V)$ extends to a $k$-automorphism of $P (V)$. Our construction uses an inseparable analogue of the Cremona transformation. We also study foliations on Drinfelds half-spaces. This leads to various examples of interesting varieties in positive characteristic. In particular, we show a new example of a non-liftable projective Calabi-Yau threefold in characteristic $2$ and we show examples of rational surfaces with klt singularities, whose cotangent bundle contains an ample line bundle.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
