Scientific journal
International Journal of Applied and fundamental research
ISSN 1996-3955
ИФ РИНЦ = 0,593

1 Ushtenov Y.R. 1
1
1093 KB

Простые числа приобретают особую важность в теории чисел в силу «фундаментальной теоремы арифметики», гласящей, что каждое составное число может быть представимо одним и только одним способом в виде произведения простых множителей [3, 7].

Первая теорема, утверждающая существование бесконечного множества простых чисел, была доказана уже Евклидом в «Началах», в книге 9, предложение 20 [3, 7].

Под критерием простых чисел понимается теоретико-числовое свойство, которое присуще лишь простым числам и наличие которого может быть установлено независимо от предварительной проверки простого числа. Простым примером является соотношение:

akul1.wmf, (1.1)

которое справедливо тогда и только тогда, когда n является простым числом. Так как слагаемые равны 1, если m делитель n, и равны нулю, если это не так, то сумма (конечная) представляет собой число d(n) делителей n, а равенство d(n)=2 характеризует простые числа. Естественно, формула (1), как и многие другие критерии, не пригодна для практических целей [6, 30].

Критерием числа на простоту является достаточное условие простоты числа. Кроме достаточных условий простоты числа также существуют необходимые условия.

Необходимым условием простоты числа является теоретико-числовое свойство числа присущее в большей степени простым числам, но это свойство могут иметь некоторые составные числа. Приведем примеры основных необходимых условий простоты числа:

1. Всякое простое число, большее 3, представимо в виде:

6k+1 или 6k–1. (1.2)

2. Если р – число простое, то верно сравнение:

р2–1≡ 0 (mod 24) (1.3)

3. Если р – число простое, то верны сравнения:

ар≡а (mod р), (a,p)=1, (1.4)

и ар-1≡1 (mod p), (a,p)=1, (1.5)

что означает, остаток от деления а р-1 на р равен 1, и соответственно остаток от деления ар на р равен а. (Малая теорема Ферма).

Существуют и другие необходимые условия простоты числа. Достаточным условием простоты числа является теоретико-числовое свойство числа присущее простым и только простым числам. Также приведем основные примеры этих условий, основанных на следующих теоремах:

1. Теорема Вильсона. Если p – число простое, то верно сравнение:

(p–1)!+1 ≡ 0 (mod p) (1.6)

Верно и обратное утверждение.

2. Теорема Лейбница. Если p – число простое, то верно сравнение:

(p–2)! – 1 ≡ 0 (mod p) (1.7)

Верно и обратное утверждение.

3. Теорема Серпинского. Если число вида p= 4k+1 и выполняется условие сравнения:

akul2.wmf +1 ≡ 0 (mod p), (1.8)

то число p – простое [5, 51-53].

Есть и другие теоремы, дающие условия простоты.

Проверка чисел на простоту на сегодняшний день является одним из самых актуальных задач в теории чисел, так как она связана с такой задачей как факторизация числа. Если проверка на простоту числа даст положительный ответ, то есть проверяемое число окажется простым, то операция факторизации числа отпадает. В случае отрицательного ответа встает задача нахождения нетривиальных делителей испытуемого числа.

Существует много тестов на простоту числа: тест Соловея-Штрассена, тест Миллера-Рабина, алгоритм Адлемана, Померанса, Румеля, алгоритм Ленстры, проверка числа теоремой Ферма, алгоритм Ленстры-Коена, алгоритмАдлемана- Хуанга (1972 г.), алгоритм Агравала, Кайалы, Саксены (2002 г.) и другие. Все вышеперечисленные методы и алгоритмы являются полиномиальными и потому являются вероятностными.

На сегодняшний день в криптографии в системе RSA открытым текстом используют многоразрядные числа, которые невозможно проверить на простоту числа со 100 процентной гарантией и невозможно разложить на простые множители (факторизация). Это связано с тем, что проверка больших чисел на простоту требует очень большое число операций, что не под силу даже суперсовременным компьютерам.

В этой статье мы хотим привести недостаток одного детерминированного алгоритма проверки числа на простоту, считающегося наиболее совершенным и потому имеющим широкое практическое применение в криптографии, а также представить новую теорему о критерии простого числа.

В книге Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. Москва, МЦНМО. 2003 г. В главе 1, §1.9 приведен детерминированный алгоритм проверки простоты на туральных чисел индийских математиков Агравала, Кайалы и Саксены (2002 г.),. Он имеет сложность O(akul3.wmf) арифметических операций (n – проверяемое число, c – некоторая абсолютная константа). Алгоритм основан на следующей теореме.

Теорема 1.71. Пусть p – нечетное натуральное число, aakul4.wmfZ(a,p)=1.

Число p является простым тогда и только тогда, когда

(x–a)p ≡ xp – a (mod p), [4, 48] (2.1)

Мы решили проанализировать эффективность этой теоремы.

Преобразуем левую часть сравнения (2.1) в следующий вид:

akul5.wmf. (2.2)

Если p – простое число, то верно сравнение:

akul6.wmf (mod p), (2.3)

и сравнение (2.1) принимает вид:

akul7.wmfakul8.wmfakul9.wmf – a (mod p), (2.4)

и последнее сравнение равнозначно малой теореме Ферма:

akul10.wmf ≡ 1 (mod p). (2.5)

Теперь рассмотрим другой случай, когда p – составное число и притом является числом Кармайкла (псевдопростое числа), например, p1= 651=3∙11∙17, p2 = 2821=7∙13∙31, p3 = 10585=5∙29∙73, p4 = 15841=7∙31∙73 и так далее. Чисел Кармайкла бесконечно много [2, 703-722].

Экпериментальные вычисления показывают, что все эти числа пройдут тест на простоту по алгоритму индийских математиков и по малой теореме Ферма и дадут ложный ответ. Далее. При p – являющимся числом Кармайкла, естественно не найдутся числа q и k такие, удовлетворяющие условиям теоремы 1.71.

В связи с этой темой приводим новую теорему в теории чисел по критерию простого числа, являющейся банальным случаем, но не встречающейся в технической литературе.

Теорема о критерии простого числа. Автор – Ущтенов Есенбек Рискулович, авторское свидетельство № 128 от 14.02.2013 год, зарегистрированное в Комитете по правам интелектуальной собственности Министерства юстиции Республики Казахстан.

Теорема. Пусть n – натуральное нечетное число. Если выполняется условие (2.6), то верно утверждение, что n – простое число.

akul11.wmf (mod n) (2.6)

Искючения составляют только числа n=9 и n=25.

Доказательство.

Так как любое натуральное нечетное составное число может иметь наименьший делитель число 3, то наибольший делитель может быть равным числу akul12.wmf. В случае, если это число имеет другие делители, то его делители будут находится в зоне между числами 3 и akul13.wmf.

Как известно, простое число n имеет два тривиальных делителя: 1 и самого себя n, и потому, не имея ни одного делителя от числа 3 и до числа akul14.wmf, при делении этого простого числа на другие натуральные числа меньшие akul15.wmf, будут давать остатки от 1 до n–1.

На основании вышесказанного имеет место выражение (2.6).

Рассмотрим исключительные случаи.

Пример 1. Пусть n=9, тогда

akul16.wmf. 1∙2∙3 = 6,

и akul17.wmf (mod 9), (2.7)

Пример 2.

Пусть n=25, тогда

akul18.wmf 1∙2∙3∙4∙5∙6∙7∙8 = 40320,

и akul19.wmf (mod 25) (2.8)

Пример 3. Пусть n=49, тогда

akul20.wmf. 1∙2∙3∙4∙5∙6∙7∙8∙9∙10∙11∙12∙13∙14∙15∙16,

и akul21.wmf (mod 25), (2.9)

потому что 7∙14=2∙49.

Из последнего примера видно, что последующие числа вида akul22.wmf, где akul23.wmf, akul24.wmf, akul25.wmf, akul26.wmf, будут иметь результат:

akul27.wmf (mod nk), (2.10)

и вследствие этого факта будут подчиняться условию (2.6), и соответственно, не будут являться простыми числами.

Теорема доказана.

Мы убедились, что теорема индийских математиков Агравала, Кайаны и Саксены 1.71 равнозначна малой теореме Ферма и поэтому не дает гарантированной простоты проверяемого числа и потому не эффективен.