知识卡片
试除法按输入位数呈指数增长
判断n是否为素数可试除至√n;若n有β位,√n的量级为2^{β/2},因此即使暂把每次除法算常数,最坏试除次数也随位数指数增长。
找到因子时还能给出一个具体素因子线索。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第31章 数论算法 · 查看原书依据
, , skipping even integers greater than 2. We can conclude that n is prime if and only if none of the trial divisors divides n. Assuming that each trial division takes constant time, the worst-case running time is , which is exponential in the length of n. (Recall that if n is encoded in binary using β bits, then β = ⌈1g(n + 1)⌉, and
参考来源
- 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[75000,80000))。
- 结论依据:原书第31.8节的素性判定方法、证人伪代码或定理;相关公式图已核对。
- 原始内容:One simple approach to the problem of testing for primality is trial division : try dividing n by each integer 2, 3, 5, 7, 9, …, , skipping even integers greater than 2. We can conclude that n is prime if and only if none of the trial divisors divides n . Assuming that each trial division takes constant time, the worst-case running time is , which is exponential in the length of n . (Recall that if n is encoded in binary using β bits, then β = ⌈ 1g( n + 1) ⌉ , and