Вдосконалений алгоритм пошуку символів Якобі

Abstract

В роботі викладено теоретичні основи пошуку символів Якобі, обґрунтовано необхідність та актуальність розробки методів пошуку символів Якобі. Проведений аналіз існуючих методів визначення квадратного лишку за модулем. Досліджено алгоритм пошуку символів Якобі. Запропоновано вдосконалений алгоритм пошуку символів Якобі. Досліджено властивості квадратів в системі залишкових класів. Здійснено оцінку складностей та проведено порівняльний аналіз розробленого та існуючого алгоритмів пошуку символів Якобі.

В работе изложены теоретические основы поиска символов Якоби, обоснована необходимость и актуальность разработки методов поиска символов Якоби. Проведенный анализ существующих методов определения квадратного остатка по модулю. Исследован алгоритм поиска символов Якоби. Предложено усовершенствованный алгоритм поиска символов Якоби. Исследованы свойства квадратов в системе остаточных классов. Осуществлена оценка сложностей и проведен сравнительный анализ разработанного и существующего алгоритмов поиска символов Якоби.

This paper describes the theoretical foundations of search characters Jacobi, the necessity and urgency of developing methods for finding characters Jacobi. The analysis of existing methods for determining remains square residue. Described algorithm for search Jacobi symbols. An improved search algorithm Jacobi symbols. The properties of squares in the system of residual classes. The estimation of the complexities and the comparative analysis of developed and existing search algorithms Jacobi symbols.