|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
Большие простые числа12.05.2012, 23:14. Показов 3569. Ответов 14
Метки нет (Все метки)
Добрый вечер. Реализовал поиск простых чисел при помощи теста миллера-рабинского. Но при больших числах(1024) бит. ВРемя поиска равняется 1 часу. Для шифрование RSA это неприемлимо. Оказалось что тормаза происходят в быстром возведении в степень(а именно в происке модуля одного большого числа по второму). Как ускорить программу.
0
|
|
| 12.05.2012, 23:14 | |
|
Ответы с готовыми решениями:
14
Даны натуральные числа a и b. Получите все простые числа большие a и меньшие b Очень большие простые числа
|
|
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
|
|
| 14.05.2012, 09:28 | |
|
быстрее возвестив степень надо использовать http://e-maxx.ru/algo/euler_function + http://e-maxx.ru/algo/chinese_theorem
0
|
|
|
|
||
| 15.05.2012, 07:27 | ||
|
А какую билиотеку для работы с длинными числами вы используете? Или свой велосипед? В большинстве есть уже готовые быстре реализации.
0
|
||
|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
| 15.05.2012, 23:14 [ТС] | |
|
Свой велоспиед. Это курсовая работа.
0
|
|
|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 5
|
|
| 21.05.2012, 16:57 | |
|
Всем привет. Скажите, кто-нибудь работал с большими числами на микроконтроллере (Cortex-M3)? Даже если нет, все равно хотелось бы уточнить некоторые моменты.
1. Правильно ли я понимаю, что для получения числа Софи Жермен, нужно сначала найти подходящее мне по размеру простое число, а затем проверить является ли оно числом Софи Жермен. Проблема еще в том (по крайней мере для меня на данный момент), что все это под МК и размер числа Софи Жермен составляет 56 байт. 2. Мне нужно только одно число Софи Жермен, но я так понимаю, что для его нахождения мне все равно придется перебирать кучу простых чисел. Или все-таки есть способ проще? 3. Правильно ли я понимаю, что если длина числа 56 байт, то это значит что число состоит из 56 цифр, каждая из которых хранится в отдельной ячейке массива для последующей работы с длинными числами.
0
|
|
|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
| 21.05.2012, 17:00 [ТС] | |
|
Необязательно. Длинна числа в одной ячейке должна быть равна макс разрядности МК/2. Т.е. на 32 битном компе в каждой ячейке хранится 32 бита т.к. среда позволяет нам работать с 64 разрядными числами. НА 8битном мк. необходимо работать с числами от 0 до F
1
|
|
|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 5
|
|
| 21.05.2012, 17:29 | |
|
Ух ты, оперативно, спасибо. Т.е. если у меня 32-х битный МК, то все это огромное число я могу разложить по ячейкам массива, каждая из которых сможет содержать число от 0 до 65535 (от 0x0 до 0xFFFF). Т.е. просто будет не 10, а другое основание. А по пунктам 1 и 2 еще не подскажите. Прото я видел алгоритмы поиска n-го количества простых чисел (в том числе и Софи Жермен) в пределах заданных значений. А вот если мне нужно одно значение определенного размера мне все равно надо последовательно получать все числа Софи Жермен до тех пор пока я не найду число длиной 56 байт или есть еще какой-то способ определить его?
0
|
|
|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
| 21.05.2012, 19:31 [ТС] | |
|
Я делал так: генерировал простое число заданой длинны. Проверяю простое ли оно. Потом увеличиваю на один пока не найду простое.
1
|
|
|
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
|
| 21.05.2012, 20:48 | |
|
domovoi94, только увеличивать на 1 смысла нет, так как получится чётное. Увеличивать надо на 2.
1
|
|
|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
| 21.05.2012, 20:53 [ТС] | |
|
Ну там проверяются значения через кумулятивный массив простых чисел и оно сразу отсеивается.
0
|
|
|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 5
|
||
| 22.05.2012, 00:16 | ||
|
Спасибо вам за идею.
0
|
||
|
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
|
| 22.05.2012, 00:25 | |
|
Начало немного не такое. Просто генерируем случайное число, длиной 56 байтов. Тут важно только убедиться что старший байт (или даже бит) не равен нулю. Ну и младший бит насильно устанавливаем в единицу, чтобы получилось нечётное. Ну, а потом увеличивая по 2 находим не только простое, но прстое С-Ж. Правда этот процесс займёт непредсказуемое количество времени.
1
|
|
|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 5
|
|
| 22.05.2012, 00:35 | |
|
Хм, спасибо, я понял. Плохо только, что процесс займёт непредсказуемое количество времени. Особенно учитывая, что все это должно крутиться на 32-битном микроконтроллере. Ладно, буду пробовать. Еще раз спасибо.
0
|
|
|
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41
|
|
| 22.05.2012, 08:33 [ТС] | |
|
Проверку нужно делать при помощи тестал -миллера рабина. На компе это занимает десятые доли секунды. Надо еще вовзведение в степень Монгомери.
1
|
|
|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 5
|
|
| 22.05.2012, 09:57 | |
|
Спасибо большое. А то я за последние 2 дня уже столько новых для себя алгоритмов увидел, что все перемешалось. Теперь хоть на чем-нибудь остановлюсь. Теперь осталось еще разобраться с длинными числами, чтобы все это можно было реализовать. Нашел библиотеку FreeLIP, но она, как, видимо, и все остальное для "большого брата", еще часто встречается GMP, но опять же для компьютера. Где-то видел, что с большими числами можно работать по принципу вычислений начальных классов - в столбик
. Алгоритм я так понимаю тупой, но лепить что-то свое из этих FreeLIP или подобного боюсь уже времени не хватит.
0
|
|
| 22.05.2012, 09:57 | |
|
Помогаю со студенческими работами здесь
15
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога
Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
|
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
|
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога
В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
|
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
|
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога
Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
|
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
|
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования.
Часть библиотеки BedvitCOM
Использованы. . .
|
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога
SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
|