Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 20 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

21
Впрочем, есть гораздо более сильный результат Юрия Матиясевича
[1970], который доказал, что существует многочлен с целыми
коэффициентами от нескольких переменных, значениями которого будут в
точности все простые числа. Приведем этот многочлен (материал взят из
лекций С.В. Сизого по теории чисел [77]):
F (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
(k + 2)(1 − (wz + h + j − q)
2
− (2n + p + q + z − e)
2
− (a
2
y
2
− y
2
+ 1 − x
2
)
2
−
−((e
4
+ 2e
3
)(a + 1)
2
− o
2
)
2
− (16(k + 1)
3
(k + 2)(n + 1)
2
+ 1 − f
2
)
2
−
−(((a + u
4
− u
2
a)
2
− 1)(n + 4dy)
2
+ 1 − (x + cu)
2
)
2
−
−(ai + k + 1 − l −i
2
− ((gk + 2g + k + 1)(h + j) + h − z)
2
−
−(16r
2
y
4
(a2 − 1) + 1 − u
2
)
2
− (p − m + l(a − n − 1)+
+b(2an + 2a − n
2
− 2n − 2))
2
− (z − pm + pla − p
2
l + t(2ap −p
2
− 1))
2
−
−(q − x + y(a −p −1) + s(2ap + 2a −p
2
− 2p − 2))
2
−
−(a
2
l
2
− l
2
+ 1 − mr)
2
− (n + l + v −y)
2
)
Следует также упомянуть, что с помощью этого многочлена Ю. Матиясевич
сумел решить знаменитую 10-ю проблему Гильберта, доказав, что не
существует общего алгоритма для определения, имеет ли произвольное
диофантово уравнение решение в целых числах. Этот результат послужил
развитию целой серии результатов о неразрешимых проблемах в различных
областях математики.
Генерация простых чисел, основанная на тесте Поклингтона
Рассмотрим один способ генерации больших простых чисел,
основанный на тесте Поклингтона (стр.19) Пусть задано простое число
p:
1. Выберем случайным образом чётное число R на промежутке p ≤
R ≤ 4p + 2 и определим n = pR + 1.
2. Проверим число n на отсутствие малых простых делителей,
разделив его на малые простые числа.
3. Выполним для числа n тест Миллера-Рабина (см.ниже на c.27) с
использованием нескольких различных баз a < p. Если при одном из тестов
                                                                                                 21

          Впрочем, есть гораздо более сильный результат Юрия Матиясевича
[1970],     который        доказал,       что      существует         многочлен         с    целыми
коэффициентами от нескольких переменных, значениями которого будут в
точности все простые числа. Приведем этот многочлен (материал взят из
лекций С.В. Сизого по теории чисел [77]):

            F (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
(k + 2)(1 − (wz + h + j − q)2 − (2n + p + q + z − e)2 − (a2 y 2 − y 2 + 1 − x2 )2 −
       −((e4 + 2e3 )(a + 1)2 − o2 )2 − (16(k + 1)3 (k + 2)(n + 1)2 + 1 − f 2 )2 −
                 −(((a + u4 − u2 a)2 − 1)(n + 4dy)2 + 1 − (x + cu)2 )2 −
            −(ai + k + 1 − l − i2 − ((gk + 2g + k + 1)(h + j) + h − z)2 −
                 −(16r2 y 4 (a2 − 1) + 1 − u2 )2 − (p − m + l(a − n − 1)+
     +b(2an + 2a − n2 − 2n − 2))2 − (z − pm + pla − p2 l + t(2ap − p2 − 1))2 −
                −(q − x + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2))2 −
                         −(a2 l2 − l2 + 1 − mr)2 − (n + l + v − y)2 )

Следует также упомянуть, что с помощью этого многочлена Ю. Матиясевич
сумел решить знаменитую 10-ю проблему Гильберта, доказав, что не
существует общего алгоритма для определения, имеет ли произвольное
диофантово уравнение решение в целых числах. Этот результат послужил
развитию целой серии результатов о неразрешимых проблемах в различных
областях математики.

Генерация простых чисел, основанная на тесте Поклингтона

          Рассмотрим один способ генерации больших простых чисел,
основанный на тесте Поклингтона (стр.19) Пусть задано простое число
p:
          1. Выберем случайным образом чётное число R на промежутке p ≤
R ≤ 4p + 2 и определим n = pR + 1.
          2. Проверим число n на отсутствие малых простых делителей,
разделив его на малые простые числа.
          3. Выполним для числа n тест Миллера-Рабина (см.ниже на c.27) с
использованием нескольких различных баз a < p. Если при одном из тестов

Страницы