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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 73
процедура не слишком удобна, поэтому для вычисления прямого вычисления
подходящих дробей удобнее реккурентная формула (2.41), приведенная в
предыдущем параграфе.
Уравнение Пелла при –1 в правой части не всегда имеет решение, что
устанавливается следующей теоремой:
Теорема 2.3. Пусть n > 0–натуральное число, не являющееся полным
квадратом. Уравнение Пелла x
2
− ny
2
= −1 имеет непустое множество
решений в том и только в том случае, если период последовательности
непрерывных дробей является нечетным числом k.
Если (x
1
, y
1
)–наименьшее (нетривиальное) решение x
2
− ny
2
= −1,
то любое другое решение (x
t
, y
t
) можно получить возведением в нечетную
степень двучлена (x
1
+ y
1
·
√
n). При возведении двучлена (x
1
+ y
1
·
√
n) в
четную степень будут получены решения уравнения x
2
− ny
2
= 1.
Пример 4. Решить уравнение x
2
− ny
2
= −1 при n = 29.
Раскладывая действительное число
√
29 в последовательность непрерывных
дробей, найдем наименьший период k = 5. Решение, соответствующее 5-й
подходящей дроби, имеет вид (x
5
, y
5
) = (70, 13). Проверим уравнение 70
2
−
13
2
·29 = −1. Квадрат двучлена 70+13
√
29 дает пару (x
2
, y
2
) = (9801, 1820),
являющуюся решением уравнения x
2
− 29y
2
= 1.
Описание алгоритма факторизации
Метод факторизации с использованием непрерывных дробей (the
continued fraction factorization method CFRAC) был разработан в 1975 г.
Мориссоном и Брильхартом (см.[40]).
Пусть n– натуральное число, которое требуется разложить.
Рассматривается уравнение Пелла
x
2
− y
2
· n = 1
и строится последовательность подходящих дробей {p
i
/q
i
}, i = 1, 2, 3, ...
Глава 2. Простые алгоритмы факторизации                                   73

процедура не слишком удобна, поэтому для вычисления прямого вычисления
подходящих дробей удобнее реккурентная формула (2.41), приведенная в
предыдущем параграфе.
      Уравнение Пелла при –1 в правой части не всегда имеет решение, что
устанавливается следующей теоремой:

Теорема 2.3. Пусть n > 0–натуральное число, не являющееся полным
квадратом. Уравнение Пелла x2 − ny 2 = −1 имеет непустое множество
решений в том и только в том случае, если период последовательности
непрерывных дробей является нечетным числом k .
      Если (x1 , y1 )–наименьшее (нетривиальное) решение x2 − ny 2 = −1,
то любое другое решение (xt , yt ) можно получить возведением в нечетную
                           √                                        √
степень двучлена (x1 + y1 · n). При возведении двучлена (x1 + y1 · n) в
четную степень будут получены решения уравнения x2 − ny 2 = 1.

      Пример 4. Решить уравнение x2 − ny 2 = −1 при n = 29.
                                √
Раскладывая действительное число 29 в последовательность непрерывных
дробей, найдем наименьший период k = 5. Решение, соответствующее 5-й
подходящей дроби, имеет вид (x5 , y5 ) = (70, 13). Проверим уравнение 702 −
                                       √
132 ·29 = −1. Квадрат двучлена 70+13 29 дает пару (x2 , y2 ) = (9801, 1820),
являющуюся решением уравнения x2 − 29y 2 = 1.

Описание алгоритма факторизации

      Метод факторизации с использованием непрерывных дробей (the
continued fraction factorization method CFRAC) был разработан в 1975 г.
Мориссоном и Брильхартом (см.[40]).
      Пусть     n–   натуральное   число,   которое   требуется   разложить.
Рассматривается уравнение Пелла

              x2 − y 2 · n = 1

и строится последовательность подходящих дробей {pi /qi }, i = 1, 2, 3, ...

Страницы