Abstract

For the purposes of cryptography it is necessary to develop effective methods and algorithms: to check the simplicity of integers; to find large prime numbers; to factorize integers.

This paper studies a generalized method for constructing algorithms to check the divisibility of integers by a given number b in various number systems by analyzing the sets of divisors of base (a given number b), prebase (number b – 1), and postbase (number b + 1). It is indicated that the rules for testing divisibility by a given number may have different complexity depending on the number system used.

The paper introduces the formulations of some theorems with proofs. The theorems are supported by concrete examples.

These theorems can formulate for many divisibility rules for any number over the any base. Some numbers are although difficult over base 10, they are easy over another base. Some numbers, such as primes, have direct rules, but some composites have combined rules.

Для целей криптографии необходимо разрабатывать эффективные методы и алгоритмы: проверки простоты целых чисел; поиска больших простых чисел; факторизации целых чисел.

В данной статье изучается обобщенный способ построения алгоритмов проверки делимости целых чисел на заданное число b в различных системах счисления путем анализа множеств делителей базы (заданного числа b), предбазы (числа b ‒ 1) и постбазы (числа b + 1). Указано, что правила проверки делимости на данное число могут иметь разную сложность в зависимости от используемой системы счисления.

В статье приводятся формулировки некоторых теорем с доказательствами. Теоремы подкреплены конкретными примерами. Эти теоремыпозволяют сформулировать множество правил делимости для любого числа в любой системе счисления. Некоторые числа, хотя и являются сложными при делении в системе счисления по основанию 10, легко делятся в системе счисления по другому основанию.