关于高斯整数连分式PQa展开，寻找迭代中点的规律

wsc810

对于4k+1的素数p,p可以写成两数的平方和，p=a^2+b^2,  其中 a 为奇数，b 为偶数。然后对 a+bI 进行连分式PQa算法展开，何时迭代中点分别为 2i, -2i , 2 , -2,  -1。

例如 13+22I 迭代中点为 2i； 21+10I 迭代中点为 -2i；9+4I迭代中点为 2 ；3+20I 迭代中点为 -2；21+4I 迭代中点为 -1

以下给出迭代算法

1. Clear[t, a]; d = 13 + 22 I; P[0] = 0; Q[0] = 1;
   
2. t[0] = (P[0] + Sqrt[d])/Q[0]
   
3. a[0] = Round[t[0]];
   
4. i = 0; While[t[i] != 1/(t[0] - a[0]) || 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] = Round[t[i + 1]];
   
9. (*If[Q[i+1]\[Equal]Q[i]||P[i+1]\[Equal]P[i],Break[]];*)
   
10. Print[{i, Q[i], P[i], a[i]}] i++];
    

复制代码

mathematica

不要再研究整数分解了，好好干活赚钱买房子娶老婆吧，
你的数学基础是远远不够做整数分解的！

mathematica

你先把椭圆曲线分解整数的算法搞明白了都不算迟，
搞明白了算法后，自己尝试写一个椭圆曲线分解整数的软件，
然后你就知道这活到底有多么难了！

wsc810

mathematica 发表于 2021-4-20 14:56
不要再研究整数分解了，好好干活赚钱买房子娶老婆吧，
你的数学基础是远远不够做整数分解的！

偶尔算算，不影响啥的

mathematica

wsc810 发表于 2021-4-20 20:01
偶尔算算，不影响啥的

先去研究椭圆曲线整数分解算法，等你搞明白了，再想着能发明一种整数分解快速算法

wsc810

本题目中，其中的一种情形也可以看做是问 d 是怎样的高斯素数时，$w^2-d*z^2=-1$有解

mathematica

wsc810 发表于 2021-4-24 07:36
本题目中，其中的一种情形也可以看做是问 d 是怎样的高斯素数时，$w^2-d*z^2=-1$有解

椭圆曲线整数分解，你理解了吗？