找回密码
 欢迎注册
楼主: 福娃PNP

[讨论] 素性检测与整数分解

[复制链接]
发表于 2008-5-15 20:03:30 | 显示全部楼层


是N还是根号N?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-15 21:00:10 | 显示全部楼层
当然是N了.
$x^2-Ny^2=1$
=> $x/y~~sqrt(N)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-16 23:24:17 | 显示全部楼层
是N,因为解不定方程x²-Ny²=1(佩尔方程),需要找到根号N的渐近分数!所以相当于求解不定方程x²-Ny²=1的时间复杂度。我现在要知道的就是这个时间复杂度。可以参考我的空间:http://hi.baidu.com/%CB%EF%CD%F2 ... 8f0ca2d9335a82.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 08:36:51 | 显示全部楼层


$sqrt(N)$的连分数循环节长度是可以计算的,但具体算法我还没查到

[ 本帖最后由 无心人 于 2008-5-17 17:48 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-17 13:10:19 | 显示全部楼层
您说的我理解不了,您能估算一下解不定方程x²-Ny²=1(指求它的最小整数解)的时间吗?N为一个200位的整数!

[ 本帖最后由 福娃PNP 于 2008-5-17 13:12 编辑 ]

评分

参与人数 1威望 +3 金币 +5 贡献 +3 经验 +5 鲜花 +3 收起 理由
mathe + 3 + 5 + 3 + 5 + 3 很不错

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 15:55:30 | 显示全部楼层
连分数分解复杂度通常应该不太高。
所以用这种方法进行因子分解可以作为一种试探的手段,但是不一定能够因子分解成功:
下面表格是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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 16:09:26 | 显示全部楼层
6当然是例外,因为它不是奇合数.
不过,对RSA来说,连分数倒是很合适.但是,可以肯定的是,求解$x^2-Ny^2=1$的复杂度不会低.
实际上,早就有人注意到这样的方法了,但是对很大的N,实际效果并没有预料中的好.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 16:11:05 | 显示全部楼层
谁来做一下试验看看对于大数的情况如何?如果也是分解成功率这么高,RSA系统我觉得都有点悬了
而关于Pell方程,可以参考
http://mathworld.wolfram.com/PellEquation.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 16:15:41 | 显示全部楼层
呵呵,我觉得对很大的N来说,求得的x,y肯定不会小.有可能是一个大到无法想象的数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-17 16:46:49 | 显示全部楼层
有可能,而且连分数分解可能周期太长,有问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 18:04 , Processed in 0.068880 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表