mathematica因子分解

wsc810

d = 4181; P[0] = 0; Q[0] = 1; pell = -1;
t[0] = (P[0] + Sqrt[d])/Q[0]
a[0] = IntegerPart [ t[0]];
i = 0; While[(t[i] != 1/(t[0] - a[0]) && P[i] != pell) || i == 1,
P[i + 1] = Q[i] a[i] - P[i];
Q[i + 1] = (d - P[i + 1]^2)/Q[i];
t[i + 1] = (P[i + 1] + Sqrt[d])/Q[i + 1];
a[i + 1] = IntegerPart[t[i + 1]];
NestWhile[ Q[i + 1]/2,Q[i+1], EvenQ];
If[Q[i + 1] == Q[i] || P[i + 1] == P[i], Break[]];
Print[{i, Q[i], P[i], a[i]}]; i++]; {i, Q[i], P[i], a[i]}

nestwhile在此程序中为何不起作用，程序的目的是让Q[i+1]只取奇数作为迭代因子。

hujunhua

Q[i+1]对于 NestWhile来说是外部变量， NestWhile并不将迭代结果，包括中间结果和最终结果，对Q[i+1]赋值。

wsc810

hujunhua 发表于 2016-12-26 21:01
Q对于 NestWhile来说是外部变量， NestWhile并不将迭代结果，包括中间结果和最终结果，对Q赋值。

我赋值后也不起作用，代码怎么写，求教！

hujunhua

1. Q[i+1]=NestWhile[#/2&,Q[i+1], EvenQ];

复制代码

wayne

NestWhile 的第一个参数是 纯函数，但你的Q不是

wsc810

1. d = 13717421; pell = -1; P[0] = 18; Q[0] = 31;
   
2. t[0] = (P[0] + Sqrt[d])/Q[0]
   
3. a[0] = IntegerPart [ t[0]];
   
4. i = 0; While[(t[i] != 1/(t[0] - a[0]) && P[i] != pell) || i == 1,
   
5. P[i + 1] = Q[i] a[i] - P[i];
   
6. Q[i + 1] = (d - P[i + 1]^2)/Q[i];
   
7. t[i + 1] = (P[i + 1] + Sqrt[d])/Q[i + 1];
   
8. a[i + 1] = IntegerPart[t[i + 1]];
   
9. If[Q[i + 1] == Q[i] || P[i + 1] == P[i], Break[]];
   
10. Print[{i, Q[i], P[i], a[i]}]; i++]; {i, Q[i], P[i], a[i]}
    

复制代码

d为要分解的数，选取适当的Q，使得JacobiSymbol[d,Q]=1,并求出PowerMod[d,1/2,Q]的值作为P,然后迭代即可
所有的$Q_n,Q_{n-1},P_n$,满足$Q_nQ_{n-1}+P_n^2=d$

mathematica

你无非就是想利用连分数分解整数,
醒醒吧,省点劲,好好做好工作,
不要在数学上花费太多的力气!

wsc810

另外一种分解的方法是令要分解的奇合数$n$等于$Q_nQ_{n-1}$,选取的参数为$P_n$,即程序当中的pell,要求的条件为$P_n$为偶数，且$P_n>|frac{Q_n-Q_{n-1}}{2}|$，计算$d=n+P_n^2$,若$\sqrt{d}$的类只有一种结构，则在它的连分数展开中是可以裂解的。
举例

1. d = 4181 + 66^2; pell = 66; P[0] = 0; Q[0] = 1;

复制代码

这里需要改进的地方为怎样合理选取$Q_0$，使得以较小的距离达到最终的迭代结果

mathematica

别人的msieve比mathematica强,
mathematica比郭先强还强,
郭都干不出来的事,你还是不要干了吧

mathematica

国外有开源的分解质因数的软件,郭都搞不定,你就别想了,
首先大整数的乘法就很难,还有素数判定,
不仅要学一堆数学知识,还要学计算机编程,学汇编之类的,
我劝你放弃吧