增乘法在算法优化中的作用

Treenewbee

蔡家雄 发表于 2023-3-16 22:56
设 \(d=2^{2n+1}+11 \) ，

求 \(x^2 - d*y^2=1\) 的最小解，

1 (19, [170, 39])
2 (43, [3482, 531])
3 (139, [77563250, 6578829])
4 (523, [81810300626, 3577314675])
5 (2059, [76292657571747809951, 1681336224678949560])
6 (8203, [69876915611822519318, 771520323981133629])
7 (32779, [80398835008645600324801235608771036666670182431880486400032257485064770658401842307691224942422999531536156600364499923056796970, 444070481702336563743442162036596677391329202863273716321349178397032836203330537445461630919283792936487491412555761435022659])
8 (131083, [712391055453831000489441596851496374586922211968388426389868928977886834600835988092416446450847, 1967638319811445164614618584089426421183233564951501613871659298300476433553720642927098589576])
9 (524299, [262370423419022052948006380362585230636886087574885576160106593835878424107999431011992139225761227061447388396667090, 362347576933161309620975692036326829940654492435422509507444016197507206937437226010673272525903902430923747403149])
10 (2097163, [66551049079488501983959284853373248448554106736699729803934265156536874676626434177518523856595115847326033553714770905049243078368745726019557433640728343803399, 45955639339182891136502078220721866137731621744981660957938911432411265785268208500581497233009913599223286111395352680221603536538078514618343979427535429580])

Treenewbee

蔡家雄 发表于 2023-3-14 18:55
费马方程 x^8+y^8=z^7 无解，

费马方程 x^8+y^8=z^6 无解，

费马方程 x^8+y^8=z^3 无解  [16, 16, 2048]
费马方程 x^8+y^8=z^5 无解  [[8, 8, 32]
费马方程 x^8+y^8=z^7 无解  [64, 64, 128]

蔡家雄

Treenewbee 发表于 2023-3-18 08:32
1 (19, [170, 39])
2 (43, [3482, 531])
3 (139, [77563250, 6578829])

若 (6n+3)^2+2 是素数，

则 2 是素数 (6n+3)^2+2 的最小原根。

Treenewbee

蔡家雄 发表于 2023-3-21 17:01
若 (6n+3)^2+2 是素数，

则 2 是素数 (6n+3)^2+2 的最小原根。

{{9,6},{13,5},{40,10},{64,6},{74,6},{139,6},{270,10},{367,5},{370,6},{405,6},{414,6},{438,6},{449,6},{530,6},{575,10},{591,5},{598,5},{620,6},{629,6},{634,6},{664,6},{724,6},{819,6},{840,6},{860,6},{875,6},{954,6},{965,7},{995,6},{1069,6},{1101,5},{1227,5},{1234,6},{1237,5},{1239,6},{1295,10},{1344,6},{1404,6},{1410,7},{1504,10},{1537,5},{1579,6},{1620,6},{1654,10},{1664,6},{1686,5},{1764,6},{1769,6},{1779,10},{1839,10},{1854,7},{1884,6},{1934,6},{1944,6},{1960,6},{1964,6},{1975,6},{1999,6}}

Treenewbee

若 7^4*(30k+7)*4+1 是素数，

则 10 是素数 7^4*(30k+7)*4+1 的原根。

有 30k+7=67，457，787，907，......
---------------------------------------------------
{{2107,12},{2917,12},{3007,12},{3127,12},{3667,12},{5197,11},{5467,12},{6007,11},{7027,11},{7357,11},{8827,11},{9427,12},{9757,12},{10687,11},{11467,11},{12247,12},{12607,11},{13717,12},{14287,12},{14677,12}}

蔡家雄

最小原根\(g=5\) 的质数公式，

—— \(g(3^{2n+1}+2^{2n+2})=5\) .

Treenewbee

蔡家雄 发表于 2023-3-23 14:19
若 4^n+7 是素数，

则 7 是素数 4^n+7 的原根。

{{1,7},{2,7},{3,7},{4,7},{5,14},{8,7},{9,13},{10,7},{14,7},{15,13},{19,7},{22,10},{39,13},{44,7},{49,7},{63,11},{80,7},{87,7}}

蔡家雄

ysr 发表于 2020-8-23 13:29
有了160，下面再算1~6000的，这样可能就全覆盖大于等于64的偶数了。时间长等会吧。

王兄：用你的快速幂运算程序，

a=10^489941871203051460959834

b=979883742406102921919669

求 a/b 的余数，如 1001/25 的余数=1，

ysr

蔡家雄 发表于 2023-3-25 19:42
王兄：用你的快速幂运算程序，

a=10^489941871203051460959834

余数是：979883742406102921919668，就是10^489941871203051460959834+1能被979883742406102921919669整除。

蔡家雄

ysr 发表于 2023-3-26 08:30
余数是：979883742406102921919668，就是10^489941871203051460959834+1能被979883742406102921919669整 ...

王兄：用你的快速幂运算程序，

a=10^1738904759975396348535314

b=3477809519950792697070629

求 a/b 的余数，如 10001/25 的余数=1，