Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | ||
---|---|---|---|
aleut |
|
||
Прочитал недавно полезную книгу Ш.Т.Ишмухаметов «Методы факторизации натуральных чисел». Автор обладает явными способностями популяризатора. Именно в этой книге нашел доказательство структуры составных чисел Мерсенна , когда делитель ( 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 Многое конечно осталось “за кадром” , но давайте сначала посмотрим на то, что “выплеснулось”, может где и ошибся, не ошибается тот кто ничего не делает. |
|||
Вернуться к началу | |||
Sonic |
|
||
Как писать формулы, читайте тут.
Советую познакомиться с новой книгой Василенко Теоретико-числовые алгоритмы в криптографии, она в Интернетах в свободном доступе. В ней есть куча суровых методов факторизации и еще больше ссылок. Еще можно посмотреть Кнута Искусство программирования, 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] на множители. А если не знаем? Простым перебором сразу получим неэффективный экспоненциальный алгоритм.Т.е. факт верен и известен, но, вроде как, бесполезен. |
|||
Вернуться к началу | |||
[ Сообщений: 2 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Комбинаторный метод факторизации чисел | 4 |
1143 |
04 янв 2017, 14:57 |
|
Детерминированный метод факторизации чисел
в форуме Численные методы |
3 |
563 |
21 июл 2016, 20:23 |
|
Комбинаторный метод факторизации чисел
в форуме Теория чисел |
0 |
231 |
04 янв 2021, 22:02 |
|
Сумма натуральных чисел
в форуме Алгебра |
2 |
190 |
13 сен 2019, 10:13 |
|
Разбиения натуральных чисел
в форуме Теория чисел |
12 |
754 |
04 апр 2019, 17:23 |
|
Задание на нахождение натуральных чисел
в форуме Начала анализа и Другие разделы школьной математики |
10 |
1117 |
15 ноя 2014, 11:19 |
|
Синусы ста последовательных натуральных чисел | 1 |
569 |
07 дек 2014, 14:34 |
|
Во множестве A натуральных чисел содержится 1
в форуме Пределы числовых последовательностей и функций, Исследования функций |
1 |
139 |
22 дек 2023, 20:16 |
|
Последовательность натуральных чисел(индукция) | 2 |
292 |
25 дек 2017, 19:27 |
|
Найти количество натуральных чисел
в форуме Теория чисел |
6 |
1107 |
16 янв 2015, 21:20 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |