2^50372821-1 is prime?

[Anatolii]

Разложить два числа на простые сомножители: 36174685195241609307058623156071588556919160765478402098322496201601656672345474748759325284881827046590027356516803981899593124234415938475264682618329 и
число:42729794125603525715143055547841755483092995668000178402159721819058632946212934122634358810443369654903315680919422431965254993373625934146121568340753562075777160944543303827990114633443890559976621265769179050210849285847094060862552713771186929087048796695403458626692604101003089934482615751828110936790711988167546352565987439985381127671490569976918658381997 и возможно этих данных хватит, чтобы доказать или опровергнуть с помощью регулярного метода,
является ли число 2^50372821-1 is prime или composite! Возможны дополнительные вычисления!

[gris]

(Оффтоп)

Надо дождаться SerjeyMinsk. Его алгоритм такие числа, как орешки щелкает. А Вы бы разбили числа пробелами через 9, а то читать неудобно.

[venco]

Anatolii в сообщении #243677 писал(а):

Разложить два числа на простые сомножители:

А вам обязательно множители нужны, или достаточно того, что они составные.

[Droog_Andrey]

Первое можно дня за 4 щёлкнуть GNFS, но знать бы, зачем?

У меня на очереди дофига других чисел

Anatolii в сообщении #243677 писал(а):

является ли число 2^50372821-1 is prime или composite!

Оно делится на 10059956081911.

[VAL]

Anatolii в сообщении #243677 писал(а):

Разложить два числа на простые сомножители: 36174685195241609307058623156071588556919160765478402098322496201601656672345474748759325284881827046590027356516803981899593124234415938475264682618329 и
число:42729794125603525715143055547841755483092995668000178402159721819058632946212934122634358810443369654903315680919422431965254993373625934146121568340753562075777160944543303827990114633443890559976621265769179050210849285847094060862552713771186929087048796695403458626692604101003089934482615751828110936790711988167546352565987439985381127671490569976918658381997

Оба составные, что Maple определяет примерно за одну тысячную секунды (Gris, выкиньте свой Excel ). А с конкретным разложением "немного" посложнее.

Цитата:

возможно этих данных хватит, чтобы доказать или опровергнуть с помощью регулярного метода,
является ли число 2^50372821-1 is prime или composite! Возможны дополнительные вычисления!

За этим к GIMPS. Они, как раз, примерно до таких чисел добрались. То, что у меня сейчас считается лишь немного (хотя это как считать поменьше.

-- 16 сен 2009, 01:52 --

Droog_Andrey в сообщении #243690 писал(а):

Anatolii в сообщении #243677 писал(а):

является ли число 2^50372821-1 is prime или composite!

Оно делится на 10059956081911.

И правда!
Андрей! А Вы это знали или быстренько в уме прикинули?

[maxal]

Делители числа $2^p - 1$, где $p$ простое, имеют вид $2kp+1$ ($k$ - целое).

$$ 10059956081911 = 2\cdot 99855\cdot 50372821 + 1.$$

[Anatolii]

Согласно данному методу можно найти и меньший делитель, возьмём пример 2*65*50372821+1=6548466731 и из него получаем, что 2^50372821-1
делится на 6548466731. Не всё очевидно, что только вероятно! Впрочем у меня нет такой программы, чтобы проверить это!

[VAL]

maxal в сообщении #243709 писал(а):

Делители числа $2^p - 1$, где $p$ простое, имеют вид $2kp+1$ ($k$ - целое).

$$ 10059956081911 = 2\cdot 99855\cdot 50372821 + 1.$$

Угу.
Цикл до 100000 с бинарным возведением с степень по модулю, вполне посильная задача. У меня на компе за 7 секунд сосчиталось.
-- 16 сен 2009, 13:36 --

Anatolii в сообщении #243762 писал(а):

Согласно данному методу можно найти и меньший делитель, возьмём пример 2*65*50372821+1=6548466731 и из него получаем, что 2^50372821-1
делится на 6548466731. Не всё очевидно, что только вероятно! Впрочем у меня нет такой программы, чтобы проверить это!

А у меня такая программа есть.
Поэтому я утверждаю, что 6548466731 делителем не является, а делитель, приведенный Андреем - наименьший.

[maxal]

Anatolii в сообщении #243762 писал(а):

Впрочем у меня нет такой программы, чтобы проверить это!

Возьмите бесплатную PARI/GP - см. topic14229.html
Код на ней примерной такой:

? p=50372821; for(k=1,10^6, if( Mod(2,2*k*p+1)^p == 1, print([k,2*k*p+1]); ); )
[99855, 10059956081911]
? ##
  ***   last result computed in 1,272 ms.

Таким образом, чтобы перебрать значения $k \leq 10^6$ потребовалось чуть более секунды.

[Droog_Andrey]

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

Андрей! А Вы это знали или быстренько в уме прикинули?

Поиск делителя с помощью Prime95 занял менее секунды.

[VAL]

Droog_Andrey в сообщении #243904 писал(а):

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

Андрей! А Вы это знали или быстренько в уме прикинули?

Поиск делителя с помощью Prime95 занял менее секунды.

Prime95 и у меня стоит. Но у меня он считает то, что сам хочет (или то, чего GIMPS хочет), у меня не спрашивает

[Droog_Andrey]

Вся фишка в файлике worktodo.txt