Функція Ойлера на множині Z[√d] та її застосування

Abstract

В роботі розглядається функція Ойлера φ(n) на множині Z [√d], де d ≠ 1 – вільне від квадратів ціле число. Отримані теоретичні результати доповнено програмною реалізацією алгоритму знаходження значення функції Ойлера для елемента n в кільці Z [√d]. Запропоновано ввести в розгляд розширений алгоритм RSA для елементів кільця Z [√d].

Described in the work of H. Elkamchouchi, K. Elshenawy i H. Shaban and also in the Koval’s PhD “Security systems based on Gaussian integers: analysis of basic operations and time complexity of secret transformations” is an RSA-algorithm over the field of Gaussian Integers which uses Euler function for elements of the ring of Gaussian Integers Z [i]. An Euler function for Gaussian Integers is explored in the Cross’es work. This paper generalises the mentioned results for the case of the principal ideal ring Z [√d] where d ≠ 1 is an arbitrary squarefree integer. Remark that by Z [√d] we mean a minimal ring, containing the ring Z and the element [√d], i.e. the ring Z √d = {a + b √d|a, b ∈ Z }. A notion of Euler function ϕ(n) for the element n ∈ Z √dis introduced and a formula to calculate its values is found. Obtained theoretical results are complemented by a software implementation of the algorithm for finding values of the Euler function for the given element n of the ring Z √d . Introduced also is an extended RSA algorithm for elements of the ring Z √d. The results can be used in further studies on algebraic number theory and theory of rings. Developed software will be used for specialists in the field of abstract algebra and applications.