Вдосконалення методу нормування в кільці p-адичних чисел

Abstract

Аналізуються методи обчислення норми елемента в кільці p-адичних чисел. Пропонується використання альтернативного методу обчислення результанта через детермінант матриці Сильвестра, що може бути застосований для розрахунку норми елемента. Наводиться наша модифікація такого метода обчислення норми через зменшену матрицю Сильвестра. В роботі показано розрахунок теоретичної складності виконання методів, а також представлено порівняння теоретичних та практичних значень обчислення норми. Результати досліджень можуть бути використані при обчислені порядку еліптичних кривих в певних системних рішеннях.

In this paper, we show the main stages of the procedure of elliptic curves order computation, which are defined over binary field. The main attention is paid to the analysis of computational complexity (time complexity) of known methods for norm computation and research the phase of normaliza-tion in the generation elliptic curves. The paper proposes the use of an alternative method of calculation resultants through determinants Sylvester's matrix, that can be used to compute the norm of the element. However, this improvement is due to computation determinant internal structure Sylvester's matrix and basic operations. This reduces the overall complexity of the norm computation for almost 30%. We provide an assessment of theoretical complexity of this method and compare with other methods of norm computation Using practical implementation of explore methods we note the similarity of theoretical and practi-cal evaluations of norm computation. The research results can be used for counting order of the elliptical curves in specific system solutions. The advantage of methods based on resultants is with using other module: is the possibility of parallelizing computations of determinant (while the analytical method cannot be parallelizing) and a lot more speed in that case. In fact, our modification of the method of norm computation is optimal in terms of computational complexity for the case when you need to switch between bases for norm computation.