Тесты на простоту

[Someone]

Да какой же тест на простоту можно придумать на основе системы счисления? Разве только условие, что младшая цифра должна быть взаимно простой с основанием системы счисления. Но это даёт так мало информации… А все существующие тесты безразличны к системе счисления, роль играет только сложность технической реализации вычислительной техники.

[Dmitriy40]

Anton_Peplov в сообщении #1214361 писал(а):

А что, изменение системы счисления как-то облегчает проверку на простоту? За счет чего?

Не то чтобы облегчает ... Но если вдруг например можно перевести число в систему с основанием 210 быстрее чем поделить то же самое число на числа 2, 3, 5, 7 - то смысл будет, т.к. в системе с основанием 210 (ну или 30) по младшей цифре можно точно установить что число составное. Как и в двоичной для числа 2. Аналогичную процедуру можно проделать и для всех первых сотен простых чисел, делить проверяемое число не на каждое простое, а на некое их произведение и проверять остаток (младшую цифру в другой системе счисления) по таблицам. Это вполне будет работать для чисел до $2^{64} \approx 1.8 \cdot 10^{19}$ или даже до $2^{128} \approx 3.4 \cdot 10^{38}$, для которых всё деление уложится в одну команду процессора (можно даже и для чисел до $2^{256} \approx 1.1 \cdot 10^{77}$, где нужно от 4-х до 8-ми команд деления процессора). Другое дело, что даже для чисел до $2^{64}$ (не говоря уж о ещё бОльших) проверка на первые тысячи простых (из более чем 200 млн) занимает доли процентов общего времени и никакого практически заметного эффекта такое ускорение не даст.

kthxbye
Так что идея, с некоторыми доработками, вполне рабочая. Но бесполезная на практике.

PS. Если кому надо, то я могу и теоретически оценить максимальный выигрыш, и даже проверить его на практике. Но сразу говорю, это будут какие-то доли процентов для достаточно больших чисел. И полезно это может быть лишь для чисел до скажем миллиона (или миллиарда), для которых общее время проверки на простоту и так измеряется в микросекундах (или в миллисекундах) и уменьшать его ещё дальше просто нет смысла.

[atlakatl]

Dmitriy40
При переводе числа в другую систему счисления мы рекурсивно делим его на новое основание (большое у ТС). Это время.
Ну перевели. А дальше те же проверки делимости на $3, 5, 7, 11, 13, ...$.
Чем проверка десятичного числа $66765088099$ сложнее проверки того же числа в 31-ичной системе: 2d7221ca?

[Dmitriy40]

atlakatl
Я написал когда и какое будет ускорение. Чем в 31-ичной сложнее или проще не знаю, а вот в 30-ичной будет быстрее т.к. можно смотреть лишь одну младшую цифру, не переводя всё число в новую систему счисления и больше уже ничего не деля. А в 510510-ичной будет ещё быстрее так как не надо отдельно делить на 2, 3, 5, 7, 11, 13, 17, а достаточно разделить лишь на 510510 и посмотреть (по таблице длиной в полмиллиона ячеек) одну младшую цифру.
Разумеется это не исключает проверки на остальные простые числа. Ускоряется/упрощается лишь проверка на первые сотни малых простых чисел, не более. О чём и говорил ТС.

Фактически можно одной командой процессора (деление, обращение к таблице намного быстрее деления) сразу отбросить 82% (для модуля 510510) чисел как составные. Вместо выполнения 6-ти делений, т.е. почти в 6 раз быстрее. Но лишь для первых малых простых чисел. И ценой размера памяти под таблицы.

[Батороев]

kthxbye в сообщении #1214344 писал(а):

Какие существуют тесты на простоту числа в которых так или иначе задействованы различные системы счисления?

Т.к. остатки от деления по модулю $m$ - это окончания чисел в $m$-чной системе счисления (выраженные в десятичной СС), то большинство тестов на простоту связаны с системами счисления.

[atlakatl]

Батороев
В тесте на простоту нас интересует только дихотомия "ноль-не ноль". Если получился ноль, то он будет нулём в любой системе.
А не ноль получится - то на систему счисления тоже смотреть не надо.

Батороев в сообщении #1214626 писал(а):

остатки от деления по модулю $m$ - это окончания чисел в $m$-чной системе счисления (выраженные в десятичной СС)

Не все остатки можно выразить - да и зачем? - в десятичной СС: цифр не хватит.

[Батороев]

atlakatl в сообщении #1214628 писал(а):

В тесте на простоту нас интересует только дихотомия "ноль-не ноль". Если получился ноль, то он будет нулём в любой системе.
А не ноль получится - то на систему счисления тоже смотреть не надо

Во многих тестах, как минимум, важны остатки и $\pm 1$.

atlakatl в сообщении #1214628 писал(а):

Не все остатки можно выразить - да и зачем? - в десятичной СС: цифр не хватит.

В десятичной системе нет числа, которое нельзя выразить. А вот придумывать написание цифр для бо́льших систем - как раз-то жизни и не хватит.

-- 07 май 2017 12:23 --

Вот например, как можно записать число: $52719_{10}=CDEF_{16}=|12|13|14|15_{\text{предлагаемой мной 16-чной}}$

[atlakatl]

Батороев в сообщении #1214626 писал(а):

остатки от деления по модулю $m$ - это окончания чисел в $m$-чной системе счисления (выраженные в десятичной СС)

Объясните - от начала до конца - что Вы написали, тогда можно говорить дальше.

[Батороев]

atlakatl в сообщении #1214638 писал(а):

Объясните - от начала до конца - что Вы написали, тогда можно говорить дальше.

В $16$-чной системе $C=12, D=13...$.
Допустим, я не знал о существовании таких цифр (или их не придумали) и тогда я записал разряды числа $16$-чной системы в десятичной форме и отделил их разделителем "$|$". Суть не изменилась.

-- 07 май 2017 12:49 --

Обратите внимание на окончание числа (последний разряд) и сравните с тем, что $52719\equiv 15 \pmod {16}$.

[atlakatl]

Батороев в сообщении #1214636 писал(а):

Во многих тестах, как минимум, важны остатки и $\pm 1$.

Как данные остатки будут меняться при переходе в другую СС?

[Батороев]

atlakatl в сообщении #1214647 писал(а):

Батороев в сообщении #1214636 писал(а):

Во многих тестах, как минимум, важны остатки и $\pm 1$.

Как данные остатки будут меняться при переходе в другую СС?

Никак. Поэтому по-видимому и используются в тестах. Впрочем, не мне - любителю - об этом судить. Вы спросили, используются ли различные СС в тестах простоты - я ответил, что "да" (в указанной мной части).
Если у Вас есть какие-то наработки, то покажите их, пожалуйста уж, не томите. А то праздничные дни утекают.

[atlakatl]

Батороев
Указанная Вами часть - остатки деления - от СС не зависит. Более того, комп проводит вычисления в двоичной системе.
А вот тестов на простоту, строго завязанных на конкретную СС, просто нет.

[Dmitriy40]

atlakatl в сообщении #1214649 писал(а):

А вот тестов на простоту, строго завязанных на конкретную СС, просто нет.

Т.е. легко проверяемое условие $n=xx \dots xx0_\text{любая система счисления} \Rightarrow n - \text{составное}$ Вы не считаете тестом на простоту?

[atlakatl]

Dmitriy40
Конечно нет. Переводить число в другие СС, чтобы увидеть, оканчивается ли оно в этой СС на ноль, тестом не является. - На практике, конечно.

[Dmitriy40]

atlakatl
Понятно. Тогда беру свои слова выше о делимости на малые простые и использованию для этого систем счисления назад. Трюк использовать можно (хотя на практике и бессмысленно), но тестом он не является, по Вашим словам. И тогда ответом ТС-у на его вопрос о возможности использования систем счислений для проверок на простоту будет "нет", т.к. простые в любой системе счисления будут простыми (и наоборот). И ни в какой системе счисления простые не будут иметь более простого вида чем в любой другой, в том числе десятичной.