информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыПортрет посетителяСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Microsoft обещает радикально усилить... 
 Ядро Linux избавляется от российских... 
 20 лет Ubuntu 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще? 14.04.05 19:35  Число просмотров: 4558
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.04.05 19:46  Количество правок: 1
<"чистая" ссылка>
> Идея (p-1)-метода в том, что если N=p*q и все делители
> числа p-1 маленькие, то p-1 само является делителем m! для
> небольшого m. Поэтому число 2^(m!)-1 обязано делится на p.
> Откуда p можно найти как НОД(2^(m!)-1 mod N, N).

Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще?

> Сначала вычисляют число 2^(m!) mod N. Это делается примерно
> так:
> a=2;
> for i=1 to m do
> a = a^i mod N;
> end do;
> m выбирается из расчета чем больше - тем лучше, но так
> чтобы вычисления занимали разумное время.

А на каждом шаге цикла почему бы НОД не вычислить и остановиться, как только НОД не будет равен 1?

> Потом просто вычисляют НОД(a-1,N). Если он равен:
> * 1 - значит, m взято слишком маленьким;
> * p - вуаля, найдет нетривиальный делитель N;
> * N - значит, m взято слишком большим (но это не так
> страшно - надо уменьшить m и повторить).

Нужели можно взять такое m, что НОД будет равен N. И что будет, если сомножители p-1 и q-1 примерно равны?

И, собственно, не так уж и часто встречается ситуация, когда наибольший делитель p-1 будет достаточно мал (чтобы p-1 был делителем m!), чтобы за разумное время прокрутить вышеуказанный цикл :(.

А поиск перебором для небольших значений можно ли ускорить, если из перебора исключить заведомо составные числа? Понятно, что каждый раз проверять число на простоту - только огромная потеря времени, но с другой стороны циклично вычислять простые числа практически не реально - медленно. Поэтому можно ли исключить из перебора в цикле числа, заведомо кратные 2, 3, 5, 7 и т. д. до разумных значений? Ведь совсем несложно выкинуть четные, даже кратные 2 или 3. Причем "масочка", которая маскирует из натурального ряда числа, заведомо кратные небольшому количеству маленьких простых будет периодическая и ее можно применять циклично.
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach