gifts2017

Обработка "Поиск простых чисел" для 1С 8.1

Опубликовал Артур Чколян (sondarium) в раздел Программирование - Практика программирования

Внешняя обработка поиска простых чисел и их произведений для 1С 8.1

Я часто думал над повсеместно используемым алгоритмом шифрования RSA. Эта система шифрования с открытым ключом обеспечивает сегодня безопасность всех банковских операций, деловой переписки и гражданского сектора. Давно ушли времена Энигмы, бомб и проблемы распределения ключей. Алиса и Боб нашли способ трепаться обо всём на свете, не опосаясь за то, что информация попадёт в третьи руки (конечно, если только сами Алиса или Боб будут хранить секрет). В чем суть RSA?

Возьмём два простых числа. Например, 7 и 11. Их произведение будет 77. Найти произведение 7 и 11 - операция умнлжения - довольно простое занятие для компьютера и человека. А вот найти простые сомножители  числа 77 - обратная задача - процесс намного более затратный. В этом и заключается суть этого метода. На этом держится вся современная информационная безопасность. Каждый год собираются умные дяденьки и выбирают новые стандарты длины этих чисел. Для всяких банковских операций и госбезопасности выбираются сомножители такой длины, что для нахождения ключа не хватит времени равного возрасту вселенной, даже если все компьютеры мира будут решать только эту задачу.

Простых чисел на всех хватит. Есть ассимптотический закон распределения простых чисел. Он не 100% точный, потому и называется ассимптотический, но ответ он даёт вполне пригодный: простых чисел хватит)) А вообще вся замарочка с простыми числами одна из наиболее интересных в теории чисел.

 Самый быстрый способ найти простые числа - запуск алгоритма решето аткина (оптимизированное решето Эратосфена). Можете в сети найти, что это такое, там всё очень просто.

Ну так вот... Как найти сомножители числа? Можно перебирать, но это долго, так тут же надо будет искать, умножать... Моя обработка создаёт таблицу произведений простых чисел. Так найти сомножители гораздо быстрее, я проверял. Для взлома она, естественно, не годится. Это всё исключительно из-за любопытства и ради удовольствия познания.

З.Ы. Единственное, что реально может угрожать методу RSA - это появление квантовых компьютеров. Так как они основаны на принципе квантовой суперпозиции (все операнды одновременно в конкретной операции, пока нет наблюдателя (опыт с пучком света и двумя щелями перед отражателем)), алгоритм запущенный на КК может быстро найти сомножители. Но во-первых, говорят, что для КК нужно ещё лет 20 (это с учётом, что не будет мировой войны, чумы или ещё какой оказии). А во-вторых, программы для КК уже давно пишут (методы Гровера, Шора и т.д.), и уже что-то придумали (новые методы шифрования) на тот случай, если кто-то вдруг резко сделает КК.

 

Спасибо за внимание! Надеюсь, Вам было интересно.

Скачать файлы

Наименование Файл Версия Размер
Обработка 23
.epf 8,44Kb
13.11.10
23
.epf 8,44Kb Скачать

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Сергей Ожерельев (Поручик) 13.11.10 21:27
Мне было интересно, хоть и не ново. Для каких целей это можно присопособить, вот что интересно.
2. Алексей Прилепский (IamAlexy) 13.11.10 21:58
решето аткина быстрее работает.
3. Артур Чколян (sondarium) 14.11.10 04:36
IamAlexy, спасибо, поправил.

Поручик, не думаю, что это сгодится для чего-то, кроме удовлетворения любопытства. Для меня в большинстве случаев это самое любопытство является директивным поводом, чтобы что-либо сделать.
4. Аркадий Кучер (Abadonna) 14.11.10 05:32
5. Алексей Прилепский (IamAlexy) 14.11.10 09:48
результаты которые показывает 1С соответствуют теории:


аткин быстрее http://infostart.ru/public/22292/
6. Ийон Тихий (cool.vlad4) 14.12.10 15:44
Я вот над чем задумался - квантовый 1С - к примеру есть накладная, сколько в ней чего есть никто не знает, зато точно есть - при каждом открытии накладной пользователем, он своим открытием воздействует на накладную и она меняется. Принцип неопределенности(запустится 1С или нет -неопределенность). Принцип суперпозиции - много пользователей будут влиять на работу друг друга причем нелинейно. Закон распределения пользователей на единицу объема комнаты. Кубит пользователя. А последовательность больше не надо будет восстанавливать - она одновременно будет последовательна и не последовательна. Больше не будет проблем с остатками, будет вычислятся вероятность нахождения товара на складе, потому вместо пакетов будут волновые пакеты :D
sondarium; Borisych; ildarovich; +3 Ответить
7. Ирина Борденюк (iren_8807) 10.10.11 01:39
Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. Только в 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.