求幂快速算法

gxqcn

刚才通过 google 得到一个非常好的链接：基础数论算法 里面介绍了不少基本的计算数论算法。

无心人

比那本 算法数论 如何？

liangbch

楼主注意休息，身体是最重要的。

gxqcn

21# 所给的链接里介绍是一些常见的基本的算法， 特色是条理较清晰，排版比较好。

gxqcn

原帖由 liangbch 于 2008-12-24 12:02 发表 楼主注意休息，身体是最重要的。

确实，所以好久没有升级 HugeCalc 的冲劲了。

无心人

给你一个理由吧 实现一个雅克比和素性证明算法

gxqcn

楼上这个早已在 V7 版中实现了。

无心人

还真没注意呢

nyy

gxqcn 发表于 2008-12-23 22:01
我琢磨了一下，其实“加法链”本身即包含了二进制法和因子法，只是其出发点不同、研究思路不同罢了。

比如 ...

我琢磨了一下，其实“加法链”本身即包含了二进制法和因子法，只是其出发点不同、研究思路不同罢了。

比如，主帖举例的： 的
二进制法的加法链为：{ 1, 2, 3, 6, 12, 13, 26, 27, 54, 55 }
因子法的加法链则为：{ 1, 2, 4, 5, 10, 20, 40, 50, 55 }

二进制法的加法链为，这个看懂了
因子法的加法链则为，这个看不懂

白新岭

这种解决问题的方法，我在解决线性不定方程满足条件的正整数解组数问题上用过，3.加法链
比方\(X_1+X_2+X_3+X_4+X_5+X_6+X_7+X_8+X_9+X_{10}=N\)，求N=20时不定方程的正整数解组数，要求变量X不能取5的倍数，也不能取除5余3的正整数，变量X取满足条件的正整数。
我们可以先算：：\(X_1+X_2=N\)，利用计算结果在计算\((X_1+X_2)+(X_3+X_4)=N\)，利用第二次结果在计算\(((X_1+X_2)+(X_3+X_4))+X_5=N\),
利用第三次结果在计算\((((X_1+X_2)+(X_3+X_4))+X_5)+(((X_6+X_7)+(X_8+X_9))+X_{10})=N\)
总共用4步获得答案，与站长提出的：求幂快速算法，大概同一种处理问题的方法。
下边是第四步的数据
N        5        6        7        8        9        10        11        12        13        14        15
5        10        11        12        13        14        15        16        17        18        19        20
6        11        12        13        14        15        16        17        18        19        20        21
7        12        13        14        15        16        17        18        19        20        21        22
8        13        14        15        16        17        18        19        20        21        22        23
9        14        15        16        17        18        19        20        21        22        23        24
10        15        16        17        18        19        20        21        22        23        24        25
11        16        17        18        19        20        21        22        23        24        25        26
12        17        18        19        20        21        22        23        24        25        26        27
13        18        19        20        21        22        23        24        25        26        27        28
14        19        20        21        22        23        24        25        26        27        28        29
15        20        21        22        23        24        25        26        27        28        29        30
N的加法运算
tj5        1        5        10        15        25        36        55        85        105        145        190
1        1        5        10        15        25        36        55        85        105        145        190
5        5        25        50        75        125        180        275        425        525        725        950
10        10        50        100        150        250        360        550        850        1050        1450        1900
15        15        75        150        225        375        540        825        1275        1575        2175        2850
25        25        125        250        375        625        900        1375        2125        2625        3625        4750
36        36        180        360        540        900        1296        1980        3060        3780        5220        6840
55        55        275        550        825        1375        1980        3025        4675        5775        7975        10450
85        85        425        850        1275        2125        3060        4675        7225        8925        12325        16150
105        105        525        1050        1575        2625        3780        5775        8925        11025        15225        19950
145        145        725        1450        2175        3625        5220        7975        12325        15225        21025        27550
190        190        950        1900        2850        4750        6840        10450        16150        19950        27550        36100
解组数的乘法运算
N        tj10
10        1
11        10
12        45
13        130
14        300
15        622
16        1195
17        2190
18        3865
19        6490
20        10526
最终统计结果（声明，是限制变量不能取5的倍数，及除5余3的正整数，变量取限制条件以外的正整数），当10个变量时，不定方程满足条件的正整数解组数为：10526组，此时N=20