← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3695.a.4

试除法按输入位数呈指数增长

理解等级:中级

判断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