Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/18: Рейтинг темы: голосов - 18, средняя оценка - 4.67
-19 / 6 / 0
Регистрация: 09.10.2010
Сообщений: 41

Большие простые числа

12.05.2012, 23:14. Показов 3569. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый вечер. Реализовал поиск простых чисел при помощи теста миллера-рабинского. Но при больших числах(1024) бит. ВРемя поиска равняется 1 часу. Для шифрование RSA это неприемлимо. Оказалось что тормаза происходят в быстром возведении в степень(а именно в происке модуля одного большого числа по второму). Как ускорить программу.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
12.05.2012, 23:14
Ответы с готовыми решениями:

Даны натуральные числа a и b. Получите все простые числа большие a и меньшие b
даны натуральные числа a и b. Получите все простые числа большие a и меньшие b. Объясните как найти простые числа?а то я совсем не поняла...

Очень большие простые числа
По причине своей неопытности, не знаю как решить данную задачу. Задача по теме длинная арифметика Можете подсказать принцип решения, а...

Докажите, что p² – q² делится на 24, если p и q – простые числа, большие 3
Докажите, что p² – q² делится на 24, если p и q – простые числа, большие 3.

14
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
Эксперт Java
 Аватар для turbanoff
4094 / 3828 / 745
Регистрация: 18.05.2010
Сообщений: 9,331
Записей в блоге: 12
15.05.2012, 07:27
Цитата Сообщение от domovoi94 Посмотреть сообщение
теста миллера-рабинского
Вы наверно хотели сказать Миллера-Рабина?

А какую билиотеку для работы с длинными числами вы используете? Или свой велосипед? В большинстве есть уже готовые быстре реализации.
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
Эксперт С++
 Аватар для grizlik78
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
Спасибо вам за идею.
генерировал простое число заданой длинны
вот с этим у меня как раз ясности полной нет. Я себе это представляю примерно так: пусть нужно число длиной 56 байт, нахожу простое и проверяю из скольки байт оно состоит, если != 56, ищу следующее простое и опять проверяю из скольки байт состоит и т.д. Или это совершенно ужасный алгоритм? А после того, как найдется простое нужной длины, добиваю его, например, двойками до числа Софи Жермен.
0
Эксперт С++
 Аватар для grizlik78
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
22.05.2012, 09:57
Помогаю со студенческими работами здесь

Перебором делителей найти простые числа в указанном диапазоне, и вывести все простые числа в поле Memo
Мне нужна программка на Delphi, которая простым перебором делителей находит простые числа в указанном диапазоне и выводит все простые числа...

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа. Простые числа это когда они делятся только...

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б
#include <stdio.h> #include <iostream> #include <conio.h> #include <math.h> using std::cout; using std::cin; using...

Найти все трехзначные простые числа. Определить функцию, позволяющую распознавать простые числа
помогите пожалуйста с программой Найти все трехзначные простые числа. Определить функцию, позволяющую распознавать простые числа.

Функцией определить простые числа, вывести все простые числа до N
Условие: С помощью сложной функции определения опредилить, является ли число простым, найти и вывести на экран все простые числа от 1 до...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
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(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru