Хочу попробовать реализовать тест Люка-Лемера ...

[Иван_85]

Хочу попробовать реализовать тест Люка-Лемера для о-о-очень больших чисел Мерсенна (порядка 39-го числа Мерсенна $M_{39}=2^{13466917}-1$ и больших).
Из википедии:
"Для установления простоты $M_p$ последовательность чисел $L_1,\, L_2,\,...\,,L_{p-1}\; (L_1=4,\; L_{k+1}=L_k^2-2(\mod M_p))$ вычисляется по модулю числа $M_p$ (т. е. вычисляются не сами числа $L_k$, длина которых растёт экспоненциально; а остатки от деления $L_k$ на $M_p$, длина которых ограничена $p$ битами). Последнее число в этой последовательности $L_{p-1}\mod M_p$ называется вычетом Люка — Лемера. Таким образом, число Мерсенна $M_p$ является простым тогда и только тогда, когда число $p$ простое, и вычет Люка — Лемера равен нулю."
Возник вопрос, как вычислить остаток от деления $L_k$ на $M_p$ $(L_k \mod M_p)$ ?

[Sonic86]

Иван_85 в сообщении #585978 писал(а):

Возник вопрос, как вычислить остаток от деления $L_k$ на $M_p$ $(L_k \mod M_p)$ ?

Ну в лоб как там ... $a \mod b$ или $a \% b$ для маленьких чисел... (на каждой итерации, естественно) Или Вы что-то специальное имеете ввиду?

[Иван_85]

$M_{39}$ имеет 4053946 цифр в десятичной системе счисления. А $L_k$ могут содержать еще больше цифр.
Для того чтобы считать в лоб нужно создать целочисленный тип данных который вмещал бы, скажем, до 1 000 000 000 десятичных цифр (это минимум 500 МБ памяти). Затем определить функции, реализующие умножение, сумму, возведение в натуральную степень и деление по модулю чисел этого типа данных.
Sonic86, Вы это имеете ввиду?

[Joker_vD]

Иван_85 в сообщении #586004 писал(а):

Для того чтобы считать в лоб нужно создать целочисленный тип данных который вмещал бы, скажем, до 1 000 000 000 десятичных цифр (это минимум 500 МБ памяти). Затем определить функции, реализующие умножение, сумму, возведение в натуральную степень и деление по модулю чисел этого типа данных.

Такие библиотеки давно существуют.

[Иван_85]

Joker_vD в сообщении #586006 писал(а):

Такие библиотеки давно существуют.

Не подскажете название такой библиотеки для Visual C++ Express ?

[Joker_vD]

Лично мне известна только WinNTL. Под линукс есть GMP — и надстройки типа CLN и той же NTL.

[Иван_85]

Joker_vD, спасибо за инфу.

[AV_77]

Joker_vD в сообщении #586011 писал(а):

Под линукс есть GMP — и надстройки типа CLN и той же NTL.

GMP можно и под виндоуз поставить.

[Joker_vD]

AV_77
Как верно подмечено в документации к WinNTL, "There are the flags to use GMP for potentially faster long integer arithmetic. See the GMP section for more details. Note that getting GMP to run on Windows is a pain in the neck. If you really want to use GMP, use Unix or Linux!"

[Иван_85]

Интересно, существует ли быстрый алгоритм возведения натурального числа в квадрат?

[Xaositect]

Joker_vD в сообщении #586024 писал(а):

Note that getting GMP to run on Windows is a pain in the neck

Есть форк GMP, называется MPIR. Одной из заявленных целей у них является лучшая поддержка Windows.

Иван_85 в сообщении #586115 писал(а):

Интересно, существует ли быстрый алгоритм возведения натурального числа в квадрат?

Раз быстрое умножение есть, то и быстрое возведение в квадрат тоже.

[Иван_85]

Xaositect в сообщении #586123 писал(а):

Раз быстрое умножение есть, то и быстрое возведение в квадрат тоже.

Но ведь возведение в квадрат более специальное умножение чем просто умножение. Поэтому для него возможно существует еще более быстрое умножение.

[venco]

Иван_85 в сообщении #586126 писал(а):

Xaositect в сообщении #586123 писал(а):

Раз быстрое умножение есть, то и быстрое возведение в квадрат тоже.

Но ведь возведение в квадрат более специальное умножение чем просто умножение. Поэтому для него возможно существует еще более быстрое умножение.

Существует, но не сильно быстрее - например в полтора раза (для оооочень больших чисел).

Кстати, строго говоря, возведение в квадрат медленнее, чем умножение, т.к. входных данных в два раза меньше, а время только в полтора раза меньше.

[Иван_85]

venco в сообщении #586153 писал(а):

Существует, но не сильно быстрее - например в полтора раза (для оооочень больших чисел).

Не подскажете, что за алгоритм?

[venco]

Вам это не надо. Используйте готовую библиотеку, например gmp, - там это уже есть.