Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Методы факторизации натуральных чисел и симметрия чисел
СообщениеДобавлено: 22 мар 2012, 10:52 
Не в сети
Начинающий
Зарегистрирован:
28 фев 2012, 11:04
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте уважаемые господа.
Прочитал недавно полезную книгу Ш.Т.Ишмухаметов «Методы факторизации натуральных чисел». Автор обладает явными способностями популяризатора. Именно в этой книге нашел доказательство структуры составных чисел Мерсенна , когда делитель ( q = 2kp + 1 ) ( стр. 48, где q – делитель числа , p – показатель степени числа, k – целое положительное число ). Очень здорово описаны « метод извлечения квадратного корня в конечных полях » и «метод факторизации Ферма » ( стр. 34, стр. 52 ), но почему то не нашел , что эти методы можно соединить. Многое прочитанное в этой книге подтверждает предположение о наличии свойств симметрии в множестве вычетов Zn. Так свойства симметрии чисел использует алгоритм RSA (стр. 7 ). Например одно из наиболее характерных свойств симметрии составных чисел . Для составного целого положительного числа “А”, являющегося произведением простых чисел “p” и “q”, в интервале { 1, 2, … , A-1 }, всегда найдется два числа “m” и “n” квадрат которых по модулю “A” равен единице ( стр. 12, стр. 84 ). Причем эти числа не равны известным числам ‘1’ и ‘A-1’ , квадрат которых по модулю “A”, для любых целых положительных чисел, так же всегда равен ‘1’. Т.е. [ m^2 = 1(mod A) ] и [ n^2 = 1(mod A) ] , а так же [ m+n = A ].
Вот пример, для числа Мерсенна М11 равного [ 2^11 – 1 ] , [ m = 622 ] и [ n = 1425 ].
Дальше все просто , извлекаем корень квадратный из ‘1’ по модулю ‘A’ , применяем метод Ферма , алгоритм Евклида и находим делители числа ‘A’.
Вот еще примеры, если делитель числа Мерсенна [ Mt = 2^t – 1 ], обозначить ‘dMt’, тогда:
dM11 = 23 dM23 = 47 dM29 = 2089 dM59 = 179951 dM67 = 193707721 dM71 = 228479
это то, что общеизвестно, теперь пропустим некоторое количество чисел и продолжим
dM167 = 2349023 dM173 = 730753 dM179 = 359 dM181 = 43441
и далее
dM241 = 22000409 dM251 = 503 dM263 = 23671 dM269 = 13822297
и далее
dM1009 = 3454817 dM1013 = 6079 dM1019 = 2039 dM1021 = 40841
Многое конечно осталось “за кадром” , но давайте сначала посмотрим на то, что “выплеснулось”, может где и ошибся, не ошибается тот кто ничего не делает.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы факторизации натуральных чисел и симметрия чисел
СообщениеДобавлено: 30 июл 2012, 18:40 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Как писать формулы, читайте тут.

Советую познакомиться с новой книгой Василенко Теоретико-числовые алгоритмы в криптографии, она в Интернетах в свободном доступе. В ней есть куча суровых методов факторизации и еще больше ссылок. Еще можно посмотреть Кнута Искусство программирования, 2-й том.

Цитата:
Например одно из наиболее характерных свойств симметрии составных чисел . Для составного целого положительного числа “А”, являющегося произведением простых чисел “p” и “q”, в интервале { 1, 2, … , A-1 }, всегда найдется два числа “m” и “n” квадрат которых по модулю “A” равен единице ( стр. 12, стр. 84 ). Причем эти числа не равны известным числам ‘1’ и ‘A-1’
Это верно. Вообще, сравнение [math]x^2 \equiv 1 \pmod{p_1^{a_1}...p_r^{a_r}}, p_j>2, a_j>0[/math] имеет ровно [math]2^r[/math] решений, они получаются через китайскую теорему об остатках из тривиальных решений [math]x\equiv\pm 1\pmod{p_j^{a_j}}[/math]. Это все легко найти, если знаем разложение числа [math]n=p_1^{a_1}...p_r^{a_r}[/math] на множители. А если не знаем? Простым перебором сразу получим неэффективный экспоненциальный алгоритм.
Т.е. факт верен и известен, но, вроде как, бесполезен. :(

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Комбинаторный метод факторизации чисел

в форуме Дискуссионные математические проблемы

borisaba

4

1143

04 янв 2017, 14:57

Детерминированный метод факторизации чисел

в форуме Численные методы

Iosif1

3

563

21 июл 2016, 20:23

Комбинаторный метод факторизации чисел

в форуме Теория чисел

borisaba

0

231

04 янв 2021, 22:02

Сумма натуральных чисел

в форуме Алгебра

serg10

2

190

13 сен 2019, 10:13

Разбиения натуральных чисел

в форуме Теория чисел

ivashenko

12

754

04 апр 2019, 17:23

Задание на нахождение натуральных чисел

в форуме Начала анализа и Другие разделы школьной математики

Elephant

10

1117

15 ноя 2014, 11:19

Синусы ста последовательных натуральных чисел

в форуме Задачи со школьных и студенческих олимпиад

Sardaana

1

569

07 дек 2014, 14:34

Во множестве A натуральных чисел содержится 1

в форуме Пределы числовых последовательностей и функций, Исследования функций

leonchik

1

139

22 дек 2023, 20:16

Последовательность натуральных чисел(индукция)

в форуме Дискретная математика, Теория множеств и Логика

_Frank__

2

292

25 дек 2017, 19:27

Найти количество натуральных чисел

в форуме Теория чисел

Trek

6

1107

16 янв 2015, 21:20


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved