普通数域筛选法 编辑
在数论中，普通数域筛选法是已知效率最高的整数分解的算法。
分解整数n需要
1
相关
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。
秀尔算法是一个于1994年发现的，以数学家彼得·秀尔命名，针对整数分解题目的的量子算法。不正式地说，它解决的题目是：给定一个整数



N


{\displaystyle N}

，找出他的质因数。在一个量子计算机上面，要分解整数



N


{\displaystyle N}

，秀尔算法的运作需要多项式时间。准确来说，该算法花费



O



{\displaystyle O}

的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的指数时间——大约



O





{\displaystyle O}}

还要快了一个指数。