:)
是N还是根号N?
当然是N了.
x^2-Ny^2=1
=> x/y~~sqrt(N)
是N，因为解不定方程x²-Ny²=1（佩尔方程），需要找到根号N的渐近分数！所以相当于求解不定方程x²-Ny²=1的时间复杂度。我现在要知道的就是这个时间复杂度。可以参考我的空间：http://hi.baidu.com/%CB%EF%CD%F2%B8%A3/blog/item/3c6428b3d58f0ca2d9335a82.html
:)
$sqrt(N)$的连分数循环节长度是可以计算的，但具体算法我还没查到
[ 本帖最后由 无心人 于 2008-5-17 17:48 编辑 ]
您说的我理解不了,您能估算一下解不定方程x²-Ny²=1(指求它的最小整数解)的时间吗?N为一个200位的整数!
[ 本帖最后由 福娃PNP 于 2008-5-17 13:12 编辑 ]
连分数分解复杂度通常应该不太高。
所以用这种方法进行因子分解可以作为一种试探的手段，但是不一定能够因子分解成功：
下面表格是mathworld给出的$x^2-Dy^2=1$在$D<=102$时的所有最小解。
比如对于D=6,其中x=5,那么$6|(x^2-1)=(5+1)(5-1)$并不能因子分解6
但是对于D=15,其中x=4,那么$15|(x^2-1)=(4+1)(4-1)$就很好的因子分解了15
通过分析前面102个数据，看出因子分解的成功率还是不错的。(我对那些奇合数分别标上用这种方法是否能够成功分解），但是需要注意，对于某些奇合数，对应解不存在
D
x
y
D
x
y
2
3
2
54
485
66
3
2
1
55(T)
89
12
5
9
4
56
15
2
6
5
2
57(T)
151
20
7
8
3
58
19603
2574
8
3
1
59
530
69
10
19
6
60
31
4
11
10
3
61
1766319049
226153980
12
7
2
62
63
8
13
649
180
63(T)
8
1
14
15
4
65(F)
129
16
15(T)
4
1
66
65
8
17
33
8
67
48842
5967
18
17
4
68
33
4
19
170
39
69(T)
7775
936
20
9
2
70
251
30
21(T)
55
12
71
3480
413
22
197
42
72
17
2
23
24
5
73
2281249
267000
24
5
1
74
3699
430
26
51
10
75(T)
26
3
27(F)
26
5
76
57799
6630
28
127
24
77(T)
351
40
29
9801
1820
78
53
6
30
11
2
79
80
9
31
1520
273
80
9
1
32
17
3
82
163
18
33(T)
23
4
83
82
9
34
35
6
84
55
6
35(T)
6
1
85(F)
285769
30996
37
73
12
86
10405
1122
38
37
6
87(T)
28
3
39(T)
25
4
88
197
21
40
19
3
89
500001
53000
41
2049
320
90
19
2
42
13
2
91(T)
1574
165
43
3482
531
92
1151
120
44
199
30
93(T)
12151
1260
45(T)
161
24
94
2143295
221064
46
24335
3588
95(T)
39
4
47
48
7
96
49
5
48
7
1
97
62809633
6377352
50
99
14
98
99
10
51(F)
50
7
99(T)
10
1
52
649
90
101
201
20
53
66249
9100
102
101
10
6当然是例外,因为它不是奇合数.
不过,对RSA来说,连分数倒是很合适.但是,可以肯定的是,求解x^2-Ny^2=1的复杂度不会低.
实际上,早就有人注意到这样的方法了,但是对很大的N,实际效果并没有预料中的好.
谁来做一下试验看看对于大数的情况如何？如果也是分解成功率这么高，RSA系统我觉得都有点悬了
而关于Pell方程，可以参考
http://mathworld.wolfram.com/PellEquation.html
呵呵,我觉得对很大的N来说,求得的x,y肯定不会小.有可能是一个大到无法想象的数.
有可能，而且连分数分解可能周期太长，有问题