2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 
Сообщение21.04.2009, 10:27 
ИСН писал(а):
Ну как. Если Вы знаете сколько-то нетривиальных делителей $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)$ и вторые множители одного оказываются не взаимно простыми с первыми множителями другого разложения, что можно использовать, но вот в каком порядке это делать, когда много делителей - не совсем ясно.

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

 
 
 
 
Сообщение26.04.2009, 13:41 
Аватара пользователя
http://www.garlic.com/~wedgingt/mersenne.html
:D

 
 
 
 
Сообщение27.04.2009, 15:30 
Droog_Andrey писал(а):
http://www.garlic.com/~wedgingt/mersenne.html

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

 
 
 
 
Сообщение28.04.2009, 20:29 
Аватара пользователя
Sonic86 писал(а):
У меня $n<200$
http://homes.cerias.purdue.edu/~ssw/cun/
:)

 
 
 
 
Сообщение30.04.2009, 17:19 
Аватара пользователя
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$ в пределах тысячи (или около того).

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

 
 
 
 
Сообщение30.04.2009, 23:29 
Аватара пользователя
Мат в сообщении #209910 писал(а):
любое простое число представимо $p=6k+1$. Откуда $p-1\div6$.

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

 
 
 
 
Сообщение01.05.2009, 08:31 
Droog_Andrey писал(а):
http://homes.cerias.purdue.edu/~ssw/cun/

Droog_Andrey писал(а):
http://www.garlic.com/~wedgingt/mersenne.html

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


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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group