Вопрос по большим простым числам

Сообщение №34726 от Bakhmatov 22 апреля 2010 г. 12:32
Тема: Вопрос по большим простым числам

Существует ли достаточно быстрый метод определения большого числа на принадлежность ко множеству простых чисел? Вопрос относится к числам a^{b}+c, где a достаточно мало (например 2 или 10), число b превышает 1000, c - некоторое целое число, и применение метода перебора делителей не представляется возможным.


Отклики на это сообщение:

> Существует ли достаточно быстрый метод определения большого числа на принадлежность ко множеству простых чисел? Вопрос относится к числам a^{b}+c, где a достаточно мало (например 2 или 10), число b превышает 1000, c - некоторое целое число, и применение метода перебора делителей не представляется возможным.

В любом приличном мат.пакете есть функции быстрой проверки заданного числа на простоту.
Есть также и специальные программы - например:

OpenPFGW


Спасибо большое за ссылку, тщательно изучу архивы! А обратился с вопросом потому что MathCAD просто завис, когда спросил у него является ли число 10^2009 + 1833 простым, вот и подумал может конкретно для чисел, заданных в такой форме есть что-то специфическое...


> Спасибо большое за ссылку, тщательно изучу архивы! А обратился с вопросом потому что MathCAD просто завис, когда спросил у него является ли число 10^2009 + 1833 простым, вот и подумал может конкретно для чисел, заданных в такой форме есть что-то специфическое...

С маткадом не знаком, но возможно вы попросили его *доказать* простоту этого числа. Число 10^2009 + 1833 является псевдопростым (в pari/gp проверка псевдопростоты занимает ~ 4 секунд), а значит с огромной вероятностью и простым, но вот строго доказать простоту числа такого размера - довольно трудоемкая задача.


> Число 10^2009 + 1833 является псевдопростым (в pari/gp проверка псевдопростоты занимает ~ 4 секунд), а значит с огромной вероятностью и простым, но вот строго доказать простоту числа такого размера - довольно трудоемкая задача.
RElf
А можно ли узнать, много ль у числа (10^2009 + 1833 - 1) натуральных делителей, не превышающих корень из этого числа?
Я к тому, что если можно определить такие делители и в случае, если их не так много, то проверить дальше число можно, поделив на все a_i+1, где a_i - вышеуказанные натуральные делители.


Извиняюсь! Поправка к предыдущему сообщению: a_i - четные натуральные делители.

Другими словами, если к примеру, число (10^2009+1833-1)/8*3*31 вдруг окажется простым, то достаточно будет проверить делимость числа (10^2009+1833) на множители: 2+1, 2*2+1, 2*2*2+1, 2*3+1, 2*2*3+1, 2*31+1, 2*2*31+1, 2*2*2*31+1, 2*3*31+1, 2*2*3*31+1, 2*2*2*3*31+1.


Определить, является ли число (10^2009+1833-1)/(8*3*31) простым в том случае если оно действительно простое, или имеет только очень большие делители - задача по трудоёмкости точно та же, что и исходная. Впрочем, в нашем случае всё проще - это число имеет достаточно малый делитель 353, а значит оно составное...


Кстати, и число (10^2009+1833-1)/(8*3*31*353) тоже составное, только там уже делители уже существенно большие... Точно факторизовать число (10^2009+1833-1) - непосильно.


> Кстати, и число (10^2009+1833-1)/(8*3*31*353) тоже составное, только там уже делители уже существенно большие... Точно факторизовать число (10^2009+1833-1) - непосильно.
Это непосильно нам с Вами.
RElf в таких делах дока , может он и сумеет факторизировать.
Если допустим, что добавится еще пяток делителей, то это будет еще не убийственно.

Суть моих рассуждений заключается в том, что если RElf говорил, что существующие программы могут определить псевдопростоту таких огромных чисел всего за несколько секунд, то по-видимому, можно находить большие простые числа, используя предложенный метод.
Например, берем большое простое число P и проверяем на псевдопростоту числа 2^nP+1 (где n - последовательные натуральные числа) до тех пор пока число не превзойдет P^2. В случае, если какое-либо число оказывается псевдопростым, то достаточно будет проверить это число на делимость на числа 2+1, 2^2+1, 2^3+1,...2^n+1, чтобы строго доказать его простоту.


> Извиняюсь! Поправка к предыдущему сообщению: a_i - четные натуральные делители.

> Другими словами, если к примеру, число (10^2009+1833-1)/8*3*31 вдруг окажется простым, то достаточно будет проверить делимость числа (10^2009+1833) на множители: 2+1, 2*2+1, 2*2*2+1, 2*3+1, 2*2*3+1, 2*31+1, 2*2*31+1, 2*2*2*31+1, 2*3*31+1, 2*2*3*31+1, 2*2*2*3*31+1.

Недостаточно. Вы вероятно имеете в виду (N-1)-метод доказательства простоты, но формулируете его неверно. Правильная формулировака - в теореме 1 по ссылке: http://primes.utm.edu/prove/prove3_1.html

Но в целом идея верная - если известны все делители числа N-1 (или же числа N+1), то доказать простоту N не составляет особого труда.

А у (10^2009+1833-1)/8*3*31 есть еще делители 353 и 86032073251, но их ко-фактор по-прежнему составной и, похоже, трудный для факторизации.

Кстати, существуют методы позволяющие доказать простоту числа, если известна лишь частичная факторизация N-1 и N+1 (но существенной их части) - см. http://primes.utm.edu/prove/prove3_3.html


> Суть моих рассуждений заключается в том, что если RElf говорил, что существующие программы могут определить псевдопростоту таких огромных чисел всего за несколько секунд, то по-видимому, можно находить большие простые числа, используя предложенный метод.
> Например, берем большое простое число P и проверяем на псевдопростоту числа 2^nP+1 (где n - последовательные натуральные числа) до тех пор пока число не превзойдет P^2. В случае, если какое-либо число оказывается псевдопростым, то достаточно будет проверить это число на делимость на числа 2+1, 2^2+1, 2^3+1,...2^n+1, чтобы строго доказать его простоту.

Это очень интересно, однако у числа 10^2009+1833-1 точно не меньше 7 делителей (дальше идёт ступор - числа просто "чудовищные"). Если делителей окажется хотя бы 9 - перебрать исходное число на делимость на всевозможные комбинации этих множителей окажется задачей непосильной для вычислительной техники. Хотя мысль очень и очень интересная!
Что любопытно - мой MathCAD вообще символьные операции над столь большими числами проводит с ошибками, которые заметны даже школьнику, например возводя в квадрат наше любимое 10^2009+1833, выдаёт в ответ отнюдь не 10^4018+3666*10^2009+3359889, а число с длинным(!) рядом цифр в конце, да ещё и оканчивающимся на цифру 5(!)
Так что даже если и факторизует число полностью - думаю, придётся посимвольно проверять, ваяя для сего макрос под Excel


> Недостаточно. Вы вероятно имеете в виду (N-1)-метод доказательства простоты, но формулируете его неверно. Правильная формулировака - в теореме 1 по ссылке: http://primes.utm.edu/prove/prove3_1.html

Я имею в виду то, что если составное число n=pm - псевдопростое (т.е. имеет остаток a^{n-1} \equiv 1 mod {n}), где простое р<\sqrt {n} и a < m, то должно быть целым число (n-1)/(a-1).

У чисел Кармайкла, по крайней мере, это так, но справедливо ли это утверждение для всех псевдопростых чисел (т.е. достаточно это или недостаточно), пока полной уверенности нет, но и опровержения не встречалось.

Это ли самое имеется в виду по приведенной Вами ссылке не знаю, т.к. английским языком, к сожалению , не владею. Вроде бы, по формулам похоже, но не во всем.


Поправка к предыдущему сообщению:
p - наименьший простой делитель числа n.


Плохо, что на данном форуме не предусмотрена правка своего сообщения (или я не могу ее найти). Поэтому перепишу полностью:
> > Недостаточно. Вы вероятно имеете в виду (N-1)-метод доказательства простоты, но формулируете его неверно. Правильная формулировака - в теореме 1 по ссылке: http://primes.utm.edu/prove/prove3_1.html

Я имею в виду то, что если составное число n=pm - псевдопростое (т.е. имеет остаток a^{n-1} \equiv 1 mod {n}), где р - наименьший простой делитель, то должно быть целым число (n-1)/(p-1).

У чисел Кармайкла, по крайней мере, это так, но справедливо ли это утверждение для всех псевдопростых чисел (т.е. достаточно это или недостаточно), пока полной уверенности нет, но и опровержения не встречалось.

Это ли самое имеется в виду по приведенной Вами ссылке не знаю, т.к. английским языком, к сожалению , не владею. Вроде бы, по формулам похоже, но не во всем.


> Я имею в виду то, что если составное число n=pm - псевдопростое (т.е. имеет остаток a^{n-1} \equiv 1 mod {n}), где р - наименьший простой делитель, то должно быть целым число (n-1)/(p-1).

Это неверное утверждение. Например, n=7957=73*109 является псевдопростым по основанию a=2, но при этом n-1=7956 не делится на 73-1=72.


> > Я имею в виду то, что если составное число n=pm - псевдопростое (т.е. имеет остаток a^{n-1} \equiv 1 mod {n}), где р - наименьший простой делитель, то должно быть целым число (n-1)/(p-1).

> Это неверное утверждение. Например, n=7957=73*109 является псевдопростым по основанию a=2, но при этом n-1=7956 не делится на 73-1=72.
Спасибо RElf за контр-пример. В противном случае, я б еще долго маялся в ложном направлении.


> Это очень интересно, однако у числа 10^2009+1833-1 точно не меньше 7 делителей (дальше идёт ступор - числа просто "чудовищные"). Если делителей окажется хотя бы 9 - перебрать исходное число на делимость на всевозможные комбинации этих множителей окажется задачей непосильной для вычислительной техники. Хотя мысль очень и очень интересная!
> Что любопытно - мой MathCAD вообще символьные операции над столь большими числами проводит с ошибками, которые заметны даже школьнику, например возводя в квадрат наше любимое 10^2009+1833, выдаёт в ответ отнюдь не 10^4018+3666*10^2009+3359889, а число с длинным(!) рядом цифр в конце, да ещё и оканчивающимся на цифру 5(!)
> Так что даже если и факторизует число полностью - думаю, придётся посимвольно проверять, ваяя для сего макрос под Excel
У меня инженерный калькулятор Windows и вовсе выдает число (10^2009 + 1833), как 1,e+2009, я и то не пугаюсь.

По существу:
Во-первых, нас должны интересовать делители, не превышающие \sqrt {10^2009+1833}.
Во-вторых, если и таких делителей будет 9 шт., то это означает, что всего "пригодными для проверки" делителями будут слагаемые выражения:
(2^3+2^2+2+1)(3+1)(31+1)(86032073251+1)...(...) - (всего 9 скобок), с добавлением числа 1, что для компьютера не так много.


Но контр-пример RElf'a (см. выше) сводит "на нет" все вышеприведенные рассуждения...
Ну, или почти все.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100