Gauss periods: orders and cryptographical applications

Experimental results on the multiplicative orders of Gauss periods in finite fields are presented. These results indicate that Gauss periods have high order and are often primitive (self-dual) normal elements in finite fields. It is shown that Gauss periods can be exponentiated in quadratic time. An application is an efficient pseudorandom bit generator.

     

有限域上的本原最优正规元

Let q be a prime or prime power and Fqn the extension of q elements finite field Fq with degree n(n1).Davenport,Lenstra and Schoof proved that there exists a primitive element α∈ Fqn such that α generates a normal basis of Fqn over Fq.Later,Mullin,Gao and Lenstra,etc.,raised the definition of optimal normal bases and constructed such bases.In this paper,we determine all primitive type I optimal normal bases and all finite fields in which there exists a pair of reciprocal elements α and α-1 such that both of them generate optimal normal bases of Fqn over Fq.Furthermore,we obtain a sufficient condition for the existence of primitive type II optimal normal bases over finite fields and prove that all primitive optimal normal elements are conjugate to each other.     

Abelian Groups,Gauss Periods,and Normal Bases

A result on finite abelian groups is first proved and then used to solve problems in finite fields. Particularly, all finite fields that have normal bases generated by general Gauss periods are characterized and it is shown how to find normal bases of low complexity.     

The Logarithmic finite element method in a multigrid setting

The Logarithmic finite element (“LogFE”) method is a novel finite element approach for solving boundary-value problems proposed in [1]. In contrast to the standard Ritz-Galerkin formulation, the shape functions are given on the logarithmic space of the deformation function, which is obtained by the exponentiation of the linear combination of the shape functions given by the degrees of freedom. Unlike many existing multigrid formulations, the LogFE method allows for a very smooth interpolation between nodal values on the coarse grid. It can thus avoid problems with regard to locking and convergence that appear in multigrid applications using only linear interpolation, especially for larger corsening factors. We illustrate the use of the LogFE method as a coarse grid algorithm, in conjunction with an atomistic finite element method on the fine grid, for calculating the mechanical response of super carbon nanotubes. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Computing special powers in finite fields

We study exponentiation in nonprime finite fields with very special exponents such as they occur, for example, in inversion, primitivity tests, and polynomial factorization. Our algorithmic approach improves the corresponding exponentiation problem from about quadratic to about linear time.

     

On the Computation of Square Roots in Finite Fields

In this paper, two improvements for computing square roots in finite fields are presented. Firstly, we give a simple extension of a method by O. Atkin, which requires two exponentiations in FM _q , when q9 mod 16. Our second method gives a major improvement to the Cipolla–Lehmer algorithm, which is both easier to implement and also much faster. While our method is independent of the power of 2 in q–1, its expected running time is equivalent to 1.33 as many multiplications as exponentiation via square and multiply. Several numerical examples are given that show the speed-up of the proposed methods, compared to the routines employed by Mathematica, Maple, respectively Magma.     

Chord Diagrams, d-Diagrams, and Knots

A method of representing knots, links, and singular knots and links by words in a finite alphabet and so-called d-diagrams is given. A representation of the chord diagram algebra by words in a finite alphabet is considered. This method, unlike coding by Gauss diagrams, allows one to consider knots and links simultaneously. An algorithm for recognition of diagrams of classical knots in terms of d-diagrams is given. Bibliography: 9 titles.     

Montgomery Multiplication in GF(2k)

We show that the multiplication operation c=a · b · r^-1 in the field GF(2^k can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2^k. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.     

On some questions related to the Gauss conjecture for function fields

We show that, for any finite field Fq, there exist infinitely many real quadratic function fields over Fq such that the numerator of their zeta function is a separable polynomial. As pointed out by Anglès, this is a necessary condition for the existence, for any finite field Fq, of infinitely many real function fields over Fq with ideal class number one (the so-called Gauss conjecture for function fields). We also show conditionally the existence of infinitely many real quadratic function fields over Fq such that the numerator of their zeta function is an irreducible polynomial.     

Separation of variables and the computation of Fourier transforms on finite groups, I

This paper introduces new techniques for the efficient computation of a Fourier transform on a finite group. We present a divide and conquer approach to the computation. The divide aspect uses factorizations of group elements to reduce the matrix sum of products for the Fourier transform to simpler sums of products. This is the separation of variables algorithm. The conquer aspect is the final computation of matrix products which we perform efficiently using a special form of the matrices. This form arises from the use of subgroup-adapted representations and their structure when evaluated at elements which lie in the centralizers of subgroups in a subgroup chain. We present a detailed analysis of the matrix multiplications arising in the calculation and obtain easy-to-use upper bounds for the complexity of our algorithm in terms of representation theoretic data for the group of interest.

Our algorithm encompasses many of the known examples of fast Fourier transforms. We recover the best known fast transforms for some abelian groups, the symmetric groups and their wreath products, and the classical Weyl groups. Beyond this, we obtain greatly improved upper bounds for the general linear and unitary groups over a finite field, and for the classical Chevalley groups over a finite field. We also apply these techniques to obtain analogous results for homogeneous spaces.

This is part I of a two part paper. Part II will present a refinement of these techniques which yields further savings.

     

Sign or root of unity ambiguities of certain Gauss sums

Gauss sums play an important role in number theory and arithmetic geometry. The main objects of study in this paper are Gauss sums over the finite field with q elements. Recently, the problem of explicit evaluation of Gauss sums in the small index case has been studied in several papers. In the process of the evaluation, it is realized that a sign (or a root of unity) ambiguity unavoidably occurs. These papers determined the ambiguities by the congruences modulo L, where L is certain divisor of the order of Gauss sum. However, such method is unavailable in some situations. This paper presents a new method to determine the sign (root of unity) ambiguities of Gauss sums in the index 2 case and index 4 case, which is not only suitable for all the situations with q being odd, but also comparatively more efficient and uniform than the previous method.     

有限域的原根在剩余理论中的应用

研究了p是正奇素数的情况下,有限域的原根在剩余理论中的应用．利用有限域Fp上原根的性质,给出了一类集合与平方剩余之间的关系,获得了这类集合所包含元素个数之间的关系,并且这个结论把关于这方面的结果从r=0推广到了r=0和2．     

Efficient parallel exponentiation in using normal basis representations

Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qⁿ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qⁿ) can be done in O((log₂n)²/log_qn) time using n/(log₂n)² processors. Hence we get a processor-time bound of O(n/log_qn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.     

Two-level stabilized nonconforming finite element method for the Stokes equations

In this article, we present a new two-level stabilized nonconforming finite elements method for the two dimensional Stokes problem. This method is based on a local Gauss integration technique and the mixed nonconforming finite element of the NCP ₁ — P ₁ pair (nonconforming linear element for the velocity, conforming linear element for the pressure). The two-level stabilized finite element method involves solving a small stabilized Stokes problem on a coarse mesh with mesh size H and a large stabilized Stokes problem on a fine mesh size h = H/3. Numerical results are presented to show the convergence performance of this combined algorithm.     

Fixed-point fast sweeping weighted essentially non-oscillatory method for multi-commodity continuum traffic equilibrium assignment problem

This work presents a fixed-point fast sweeping weighted essentially non-oscillatory method for the multi-commodity continuum traffic equilibrium assignment problem with elastic travel demand. The commuters’ origins (i.e. home locations) are continuously dispersed over the whole city with several highly compact central business districts. The traffic flows from origins to the same central business district are considered as one commodity. The continuum traffic equilibrium assignment model is formulated as a static conservation law equation coupled with an Eikonal equation for each commodity. To solve the model, a pseudo-time-marching approach and a third order finite volume weighted essentially non-oscillatory scheme with Lax–Friedrichs flux splitting are adopted to solve the conservation law equation, coupled with a third order fast sweeping numerical method for the Eikonal equation on rectangular grids. A fixed-point fast sweeping method that utilizes Gauss–Seidel iterations and alternating sweeping strategy is designed to improve the convergence for steady state computations of the problem. A numerical example is given to show the feasibility of the model and the effectiveness of the solution algorithm.     

A numerical algorithm for some singularly perturbed boundary value problems

A numerical algorithm is proposed to solve singularly perturbed linear two-point value problems. The method starts with a partial decoupling of the system to obtain two independent subsystems, fast and slow components. Each subsystem is then solved separately. A second-order finite difference scheme is used for this purpose. Numerical examples will be presented to show the efficiency of the method.     

Elements with prime and small indices in bicyclic biquadratic number fields

We give necessary and sufficient conditions for the existence of primitive algebraic integers with index A in totally complex bicyclic biquadratic number fields where A is an odd prime or a positive rational integer at most 10. We also determine all these elements and prove that there are infinitely many totally complex bicyclic biquadratic number fields containing elements with index A.     

Elimination with Noninvertible Pivots

A method for carrying out the Gauss elimination solution of linear systems is presented. The novelty arises from the fact that the pivot matrices are not required to be invertible, so that, for example, a scalar pivot may be zero, and a matrix pivot may be rectangular or singular. The need to execute the elimination algorithm in such circumstances arose in connection with a finite element solution of the Navier-Stokes equations in velocity-pressure variables. This application is briefly discussed, as is a method for the implementation of the algorithm.     

Discretization by finite elements of a model parameter dependent problem

The discretization by finite elements of a model variational problem for a clamped loaded beam is studied with emphasis on the effect of the beam thickness, which appears as a parameter in the problem, on the accuracy. It is shown that the approximation achieved by a standard finite element method degenerates for thin beams. In contrast a large family of mixed finite element methods are shown to yield quasioptimal approximation independent of the thickness parameter. The most useful of these methods may be realized by replacing the integrals appearing in the stiffness matrix of the standard method by Gauss quadratures.     

A Simple Finite Element Method for the Reissner-Mindlin Plate

1.IntroductionTheReissner-MindlinmodeldescribesthedefOrmationofaplatesubjecttoatrans-verseload.Thismodel,aswellasitsgeneralizationtoshells,isfrequentlyusedforp1atesandshellsofsmalltomoderatethickness.Itiswellknownthatmanynumeri-calschemesforthismodelaresatisfactoryonlywhenthethicknessparametertisnottoosmal1.Foraverysmallt,somebadbehaviors(suchaJsthelockingphenomenon)mightoccur.Inl986,F.BrezziandM.Fo.ti.l2]derivedanequivalentformulationoftheReissner-MindlinplateequationsbyusingtheHelmholtz…