Тест простоты

[serega57]

VAL в сообщении #823998 писал(а):

Поэтому и проверять множители имеет смысл только до корня из $a$

В первые на это обратил внимание и дал пояснения был ФИБОНАЧЧИ. А что касается вашего ответа то это только если квадратный корень из а меньше целого значения если больше то надо маленько поменьше. Чем квадратный корень.

[INGELRII]

Ну-ка я попробую свои силы.

Итак, у нас есть число $N$. Мы пробегаем простые числа до $\sqrt{N}$ включительно, и ни одного делителя не нашли. Ваш вопрос такой: почему мы останавливаемся на $\sqrt{N}$, правильно?

Ответ: потому что если среди чисел до $\sqrt{N}$ делителей нет, то и дальше их уже не будет, так что проверять смысла нету - это пустая потеря времени. Ваш следующий вопрос такой: а почему это их не может быть, верно?

Ответ: ну хоршо, предположим, что у $N$ нет делителей, меньше или равных $\sqrt{N}$, но есть делители $p_1$ и $p_2$ больше $\sqrt{N}$, такие что $p_1 p_2 = N$. Видим противоречие (в чем заключается противоречие, вы уже сами догадались). А раз мы получили противоречие, то наше предположение "предположим, что у $N$ нет делителей, меньше или равных $\sqrt{N}$, но есть делители $p_1$ и $p_2$ больше $\sqrt{N}$" было неверным. Чо и требовалось доказать.

[Gts]

У меня крутились разрозненные мысли: "Если мы будем перебирать делители от 2 и дальше, то первый встретившийся делитель остановит поиск". Я смутно понимал, что вот этот "первый" делитель как-то связан с $d_1 \leqslant \sqrt{d_1 \cdot d_2}$. Позже до меня дошло, что раз он первый, то он самый маленький, минимальный.

Была еще такая попытка: $N = \sqrt{N} \cdot \sqrt{N}$. Число N состоит из двух одинаковых множителей. Если мы не нашли делителей от 2 и до $\sqrt{N}$ (если в одном сомножителе нет делителей), то мы ведь не должны их найти и в другом сомножителе, так как они равны друг другу. Или если первый сомножитель $\sqrt{N}$ не разложить на множители, то второй сомножитель $\sqrt{N}$ так же не разложится на множители. Но понимал я этот факт очень смутно. Было сомнение, а вдруг если я возьму кусочек от второго сомножителя, тогда первый сомножитель может быть разложится. И куда только в этот момент девалось знание о том, что сомножители равны...

Теперь же, благодаря объяснению INGELRII, я понял объяснение VAL'а.
У меня же была вся нужная информация, как я не увидел этого...

Всем огромное спасибо за объяснения и терпение.


У меня еще осталось три вопроса.
Я увидел, что факт $d_1 \leqslant \sqrt{d_1 \cdot d_2}$ истинный. Обе части неравенства $d_1 \leqslant d_2$ я умножил на $d_1$, а потом извлек квадратный корень.
Мне интересно как пришли к такому факту, имея лишь неравенство $d_1 \leqslant d_2$? Как находят "оценку сверху для $d_1$"? И я надеюсь, что после ответа на этот вопрос смогу понять: почему эта оценка наилучшая.

И третье... по поводу того, что можно искать делители только до половины числа.
$d_1 \leqslant \frac {d_1 \cdot d_2} 2$
$2d_1 \leqslant {d_1 \cdot d_2}$
Я пытаюсь проделать аналогичные действия, которые я делал, когда у нас был корень. Но снова затык.

[Gts]

Ох... все вопросы снимаются. Я искал что-то сложное, а его там и не было. Еще раз всем спасибо.

[serega57]

Gts в сообщении #824836 писал(а):

Теперь же, благодаря объяснению INGELRII, я понял объяснение VAL'а.

Gts в сообщении #824951 писал(а):

Еще раз всем спасибо

Спасибо думаю прежде временно. Ибо всё что Вам здесь пояснили прокатит для небольших чисел. А когда N очень большое то квадратный корень из N это перебор. Как вы правильно заметили он имеет ограничения.

[serega57]

VAL в сообщении #823998 писал(а):

Поэтому и проверять множители имеет смысл только до корня из $a$.

_Ivana в сообщении #823681 писал(а):

Представьте, что у вас очень большое число для проверки, и вам надо минимизировать количество операций.

Я ведь задачу с аналогичной темой задал именно для этого. Почему сразу пошли наезды. Если теперь всех Вас спросить до какого значения брать простые делители Вы что скажите.

[serega57]

Ребята тут в вики смотрел также поясняют что брать до квадратного корня. А ещё

В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими Ясно что способ чуть улучшился это маленько как то влияет на криптостойкость

[serega57]

serega57 в сообщении #826343 писал(а):

VAL в сообщении #823998 писал(а):

Поэтому и проверять множители имеет смысл только до корня из $a$.

_Ivana в сообщении #823681 писал(а):

Представьте, что у вас очень большое число для проверки, и вам надо минимизировать количество операций.

Я ведь задачу с аналогичной темой задал именно для этого. Почему сразу пошли наезды. Если теперь всех Вас спросить до какого значения брать простые делители Вы что скажите.

Может всё таки кто не будь ответит до каких значений,для теста простоты брать простые делители.

[Руст]

Делите вначале примерно до $c\log_2(N)$. Число $c$ порядка 1000 если не превосходит квадратного корня.
Далее, если число не имело делителей или осталось все еще очень большое не факторизованное число, приступайте к более эффективным методам факторизации.

Если нужна только проверка простоты (без факторизации), то коэффициент в предыдущем можно взять поменьше и
проверять по тесту Рабина Миллера доверяя обобщенной гипотезе Римана достаточно проверять по основаниям до $2\ln^2n$.

[serega57]

Руст в сообщении #827764 писал(а):

Делите вначале примерно до $c\log_2(N)$. Число $c$ порядка 1000 если не превосходит квадратного корня.
Далее, если число не имело делителей или осталось все еще очень большое не факторизованное число, приступайте к более эффективным методам факторизации.

Если нужна только проверка простоты (без факторизации), то коэффициент в предыдущем можно взять поменьше и
проверять по тесту Рабина Миллера доверяя обобщенной гипотезе Римана достаточно проверять по основаниям до $2\ln^2n$.

Для любого числа. В прочем у моей задачи есть тоже достаточное количество вопросов также ещё намного сокращающие тест. Моё утверждение в задачи оказалось верным. По вашему задача тривиальна.

[serega57]

Руст в сообщении #827764 писал(а):

Делите вначале примерно до $c\log_2(N)$. Число $c$ порядка 1000 если не превосходит квадратного корня.
Далее, если число не имело делителей или осталось все еще очень большое не факторизованное число, приступайте к более эффективным методам факторизации.

Если нужна только проверка простоты (без факторизации), то коэффициент в предыдущем можно взять поменьше и
проверять по тесту Рабина Миллера доверяя обобщенной гипотезе Римана достаточно проверять по основаниям до $2\ln^2n$.

А почему тогда так называемый метод хакерских отак используют метод сплошного перебора. Не испульзуют Ваши предложения.