素性检测与整数分解

无心人

是N还是根号N?

medie2005

当然是N了. $x^2-Ny^2=1$ => $x/y~~sqrt(N)$

福娃PNP

是N，因为解不定方程x²-Ny²=1（佩尔方程），需要找到根号N的渐近分数！所以相当于求解不定方程x²-Ny²=1的时间复杂度。我现在要知道的就是这个时间复杂度。可以参考我的空间：http://hi.baidu.com/%CB%EF%CD%F2 ... 8f0ca2d9335a82.html

无心人

$sqrt(N)$的连分数循环节长度是可以计算的，但具体算法我还没查到 [ 本帖最后由 无心人 于 2008-5-17 17:48 编辑 ]

福娃PNP

您说的我理解不了,您能估算一下解不定方程x²-Ny²=1(指求它的最小整数解)的时间吗?N为一个200位的整数! [ 本帖最后由 福娃PNP 于 2008-5-17 13:12 编辑 ]

mathe

连分数分解复杂度通常应该不太高。 所以用这种方法进行因子分解可以作为一种试探的手段，但是不一定能够因子分解成功： 下面表格是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

medie2005

6当然是例外,因为它不是奇合数. 不过,对RSA来说,连分数倒是很合适.但是,可以肯定的是,求解$x^2-Ny^2=1$的复杂度不会低. 实际上,早就有人注意到这样的方法了,但是对很大的N,实际效果并没有预料中的好.

mathe

谁来做一下试验看看对于大数的情况如何？如果也是分解成功率这么高，RSA系统我觉得都有点悬了 而关于Pell方程，可以参考 http://mathworld.wolfram.com/PellEquation.html

medie2005

呵呵,我觉得对很大的N来说,求得的x,y肯定不会小.有可能是一个大到无法想象的数.

mathe

有可能，而且连分数分解可能周期太长，有问题