Разложить на множители 2^n-1

[Sonic86]

Вопрос такой:
Есть ли какой-то специфический, более быстрый способ разложить на множители числа вида $2^n-1$, где $n$ - составное (у меня $n=p-1$, где $p$ - простое), чем скажем, обычные способы.
У меня Maple, если он знает - скажите, этого хватит, а то когда $n=200$ он у меня начинает торомзить.

[ИСН]

Ну как. Если Вы знаете сколько-то нетривиальных делителей $n$, то тем самым знаете и столько же нетривиальных делителей $2^n-1$. А есть ли у Клёна готовая функция, которая умеет использовать такое знание для ускорения полной факторизации, или же её надо самому писать - то мне неведомо.

[RIP]

Способов не знаю, т.к. не интересуюсь, но может стоит поставить PARI/GP. При $n=200$ он разложил его на множители в доли секунды (при том, что комп у меня не самый современный, мякго говоря). maxal писал про этот калькулятор где-то рядом.

[Sonic86]

ИСН писал(а):

Ну как. Если Вы знаете сколько-то нетривиальных делителей $n$, то тем самым знаете и столько же нетривиальных делителей $2^n-1$. А есть ли у Клёна готовая функция, которая умеет использовать такое знание для ускорения полной факторизации, или же её надо самому писать - то мне неведомо.

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

RIP писал(а):

Способов не знаю, т.к. не интересуюсь, но может стоит поставить PARI/GP. При $n=200$ он разложил его на множители в доли секунды (при том, что комп у меня не самый современный, мякго говоря). maxal писал про этот калькулятор где-то рядом.

Спасибо, попробуем.

Сама по себе задача тоже может быть интересная. К примеру $2^{pq}-1=(2^p-1)(2^{pq-p}+...+1)$ и $2^{pq}-1=(2^q-1)(2^{pq-q}+...+1)$ и вторые множители одного оказываются не взаимно простыми с первыми множителями другого разложения, что можно использовать, но вот в каком порядке это делать, когда много делителей - не совсем ясно.

[Sonic86]

Maple разлагает такие числа по общему алгоритму. Если ввести $2^178-1$ то надолго виснет, а если $2^89-1$ и $2^89+1$ по одному, то очень быстро.

[Droog_Andrey]

http://www.garlic.com/~wedgingt/mersenne.html

[Sonic86]

Droog_Andrey писал(а):

http://www.garlic.com/~wedgingt/mersenne.html

Спасибо! У меня $n<200$, поэтому скорее всего без злобных извращений с числами Мерсенна обойдуся
Кстати, я там не нашел список факторизованных. В смысле - он там есть, но выглядит как-то странно.

[Droog_Andrey]

Sonic86 писал(а):

У меня $n<200$

http://homes.cerias.purdue.edu/~ssw/cun/

[maxal]

Sonic86 в сообщении #206643 писал(а):

Сама по себе задача тоже может быть интересная. К примеру $2^{pq}-1=(2^p-1)(2^{pq-p}+...+1)$ и $2^{pq}-1=(2^q-1)(2^{pq-q}+...+1)$ и вторые множители одного оказываются не взаимно простыми с первыми множителями другого разложения, что можно использовать, но вот в каком порядке это делать, когда много делителей - не совсем ясно.

В общем случае здесь работает формула (36), и задача таким образом сводится к разложению значений круговых многочленов в точке $x=2$.

Но в данном случае, как уже было справедливо замечено, можно воспользоваться Cunningham Project, где уже разложены числа вида $b^n\pm 1$ для маленьких $b$ и $n$ в пределах тысячи (или около того).

[Мат]

Sonic86
Если $n=p-1$, где $p$ простое, то полином $2^{p-1}-1$ будет делиться на все полиномы $2^k-1$, где $k$ - простые делители числа $p-1$, либо их степени. Очевидным делителем является число $2$, т.к. любое простое число представимо $p=2k+1$.
Таким образом, все полиномы $2^{p-1}-1$ делятся нацело на 3.

[Xaositect]

Мат в сообщении #209910 писал(а):

любое простое число представимо $p=6k+1$. Откуда $p-1\div6$.

Как насчет 5 или 11?
Правильное утверждение выглядит так:
Любое простое число $p \geq 5$ представимо в виде $p = 6k+1$ или $p = 6k-1$

[Sonic86]

Droog_Andrey писал(а):

http://homes.cerias.purdue.edu/~ssw/cun/

Droog_Andrey писал(а):

http://www.garlic.com/~wedgingt/mersenne.html

Спасибо большое! Нашел то, что нужно

maxal писал(а):

Но в данном случае, как уже было справедливо замечено, можно воспользоваться Cunningham Project, где уже разложены числа вида для маленьких и в пределах тысячи (или около того).

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