Да отличная статья, иногда в рамках развлечения нравится выдавить пару тактов в какой-нибудь литкодной задачке, и уверен, что найду применение прочитанному.

zkutch Sep 29 at 11:58

Разумеется написанно понятно-непонятно это очень личное дело и я понимаю таварисча сверху, но и вас понимаю. Вы старались написать хорошо, но, без обид, с моей точки зрения вы чересчур увлеклись деталями типа лемира-дюма-ньютона не выделив и не окончив главного. Например: 1. что на входе метода Монтгомери и что на выходе, 2. как уходят в форму Монтгомери и как из нее возвращаются, 3. почему это плохо для умножения и хорошо для возведения в степень и т.д. Но, опять-таки, это мои соображения и, возможно, кому-то как-раз они и покажутся неудобными. Сам Монтгомери в своей, можно сказать уже классической статье от 1985г., тоже может казаться кому-то неудобно написанным. Мне, например, видится материал отлично изложенным в Richard Crandall, Carl B. Pomerance - Prime numbers_ a computational perspective. Кому-то, кому кажется здесь изложенное заумным, может зайдет эта книга. А может и нет. Есть, кстати и русский перевод.

NikolayTheSquid Jul 11 at 21:11

Привет! Тема выбрана интересная. Но есть несколько пожеланий по форме подачи материала.

1. Мне кажется, было бы лучше организовать повествование от общего к частному. Сначала объяснить основную идею. Чтобы проще было понять хочешь ты это читать или нет. Детали реализации дать в конце, может быть в отдельном подразделе, или вообще ссылкой на код. Написать код все потенциальные заинтересованные лица здесь и сами смогут.

2. Я думаю, что в рамках формата статьи подавать материал нужно более простым языком. Желательно без формул. Совсем идеально было бы картинкой. Куда там какой разряд идёт. Как в самоучителе по математике, а не как в учебнике.

3. На мой взгляд, чем короче изложение, тем лучше. Потому, что у человеков размер окна внимания весьма ограничен. Тем кто не ещё знаком с информацией, приходиться это окно мучительно по тексту перемещать. А тем, кто знаком и у кого информация уже в памяти есть, тем читать смысла нет.

Посмотрел темы остальных публикаций в профиле. Вроде бы тоже обещает быть интересно. Сохранил себе в закладки на будущее.

Ruimteschroot Jul 15 at 17:19

Стоит показать, что строчку
long t = (T - m * N) >>> 32; можно заменить на
long t = (T >> 32) - (m * N) >> 32; То есть для произведения m * N нужные только верхняя часть результата.

А значит на языке java, где пока нет 128-битного типа данных, для 64-битных чисел можно написать что-то вроде:

static long redc(long Thi, long Tlo, long N, long M) { long m = Tlo * M; long t = Math.unsignedMultiplyHigh(m, N);

return Thi - t + (Thi < t ? N : 0); }

static long montgomeryMultiply(long a, long b, long N, long M) { return redc(Math.unsignedMultiplyHigh(a, b), a * b, N, M); }

Получается для умножения Монтгомери нужно сделать:
одно полное умножение;
одно умножение с получением верхней части результата
одно умножение с получением нижней части результата

Кстати, умножение Монтгомери можно делать и тогда когда только одно число в форме Монтгомери, тогда результат будет тоже не в форме.

1kovand1 Jul 18 at 20:43

$m(a) = aR \pmod{N} = \lfloor aRMN / 2^{128}\rfloor\pmod{2^{64}}$
$aR\cdot M$ — это 192-битное число, но нам достаточно вычислить младшие 128 бит. Остальные исчезнут при вычислении $\mod{2^{64}}$ .