ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
6 сообщений из 6, страница 1 из 1
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429254
Sarin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sarin
Участник
Не может же такого быть, чтобы эту задачу никто не решал. Я столкнулся с такой проблемой:
надо получить некое значение (a s - 1) mod n
Показатель степени s есть произведение некоторых чисел. Пусть будет x, y, z. Тоесть:
(a s - 1) mod n = (a x * y * z - 1) mod n
a s - очень большое число. И когда его длинна стала превышать 200000 десятичных знаков мой компьютер дальше считать отказался.

Кто помнит, к чему приводится вот такое выражение: a a * b * c ? Этоже ещё в школе было. Я забыл просто:(

Код: plaintext
ROLLBACK;
...
Рейтинг: 0 / 0
31.03.2007, 16:14
| Ответить | Цитировать | Написать  
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429281
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
((A**a)**b)**c если это конечно поможет :)
...
Рейтинг: 0 / 0
31.03.2007, 17:03
| Ответить | Цитировать | Написать  
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429283
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SarinИ когда его длинна стала превышать 200000 десятичных знаков мой компьютер дальше считать отказался.

Гром и молния! Этого не может быть!!
...
Рейтинг: 0 / 0
31.03.2007, 17:08
| Ответить | Цитировать | Написать  
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429307
Sarin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sarin
Участник
mayton SarinИ когда его длинна стала превышать 200000 десятичных знаков мой компьютер дальше считать отказался.

Гром и молния! Этого не может быть!!
Чего не может быть?
...
Рейтинг: 0 / 0
31.03.2007, 17:48
| Ответить | Цитировать | Написать  
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429325
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SarinЧего не может быть?

Такие числа в природе не существуют и применения не находят в принципе. Другое дело, что они могут быть ПРОМЕЖУТОЧНЫМ результатом каких-то вычислений (напр вычисление факториала), но как РЕЗУЛЬТАТ они лишены смысла. Посмотрите внимательно на свою формулу. В конце стоит операция mod n . Это означает, что каких-бы точностей вы не достигали, разрядность результата будет усечена до [Log10(n)] разрядов. Следовательно вам не нужна операция возведения в степень. Вам нужно ВОЗВЕДЕНИЕ В СТЕПЕНЬ ПО МОДУЛЮ N .

Это руководство к оптимизации.
...
Рейтинг: 0 / 0
31.03.2007, 18:19
| Ответить | Цитировать | Написать  
Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
    #34429452
Sarin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sarin
Участник
mayton
Точняк, факторизация. За совет спасибо. Очень хотелось самому что-то всётаки придумать по оптимизации.
...
Рейтинг: 0 / 0
31.03.2007, 22:13
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Кто помнит школьную арифметику? Алгоритм Поллрада p-1. Часть вторая:)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=165&tid=1346160]:
 0ms
get settings:
 9ms
get forum list:
 17ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 45ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 42ms
get tp. blocked users:
 1ms
others: 217ms
total:  346ms
созд. / загр.: 346ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]