每一个整数，在理论上都能被分解为素因子，但要做到这一点，所费时间可能超过宇宙存在的期限。用初等易见的方法，即逐个地用素数试除它，直除到此数的平方根为止，是无望的。它的运算时间增长得如此之快，举例说，如果将计算机运算速度加快100倍，也只能使所能处理的数字的大小略加几个数位。要分解一个250位的数——如果不是那种特殊形式易于分解的数——现在是不可能做到的。
另一方面，还未有人证明素数分解真应当如那样的难。有效有力的方法的可能性还没有被排除。由阿姆斯特丹大学伦斯特拉（Hendrik lenstra）设计，根据代数几何和数论的高深概念的新方法（“用椭圆曲线分解素因子”），指出了进攻的新方向。这个问题具有实际重要性，是因为它与公开密码有关——这种公开密码是一种将文电编成密码的方法，被认为是“不可破译的”，但如果存在一种快速分解因子算法，某些这类密码将是可破译的。这个问题作为数论中最基本的问题之一，也具有它内在的数学趣味。
研究的对象是算法：一种预定的程序，其中不可用猜测法，它能保证产生一个因子，或者证明这个数本身是素数。这种算法的效率是根据它的“运转时间”（以最坏情况计数）随着n（被分解数的位数）增长的方式来衡量的。这个运转时间通常被定义为其中算术运算（加，乘，等等）的次数，对此我们仅能作相当粗略的估计。一个“好”算法以多项式时间运转，即它的增长不快于n的某个固定幂的幂函数，而坏算法以指数时间运转，按某个常数的n次幂即指数函数的速度增长。
对于一个n位数，其大小略为10n，大约需要10n/2次试除。仅逐个试除一项算术运算，这个次数已经是以指数函数增长（这是一个太低的估计），因此是无效的。作为对比，用欧几里德算术求两个n位数的最小公倍数，仅需大约5n步。所以这以多项式时间运转，是高度有效的。
要说明这些有别于试除的算法，我将先描述波拉德（pollard）的p-1方法。这个方法从数N开始，并寻求它的使得p-1仅有“小”素因子的那些素因子P。它根据这个数论定理：如果p-1整除数Q，而P不能整除Q，则P整除αQ-1，这里α是任一不被p整除的数。则N与αQ-1的最小公倍数被p整除，这个最小公倍数可通过欧几里德算术迅速地求出来。在实际执行过程中，有一系列Q被给出并储存在计算机中：例如，令Q为整数集合（1，2，…r）的最小公倍数，这里r=1，2，3，…直至一个预定的上限。作为一个例子，这个方法已用来找到数3130+1的素因子P=2670091735108484737。虽然p很大，但P-1可分解成27· 32· 72· 172· 19 · 569 · 631 · 23993，这里都是小素数。
伦斯特拉方法的要点是以更抽象的术语构思波拉德的算法。假定P是素数，如果在数集（1，2，…p-1）中作任意两个数的关于模P的乘法（即取两数乘积用P除所得的余数），则所得乘积仍属于这个集合。我们说这个集合形成关于模P的乘法群。波拉德方法可以被理解为对此群结构的利用。伦斯特拉方法来自波拉德方法，但用更精巧的群取代了后者的群，这个新群是由椭圆曲线上的点构成的群。
数论学家们研究椭圆曲线已有大约一个世纪之久，可不是为了它对分解素因子的应用而是由于它们内在的数学美感和趣味。这些曲线由形如用y2=x2+ax+b的方程所定义，这里a，b是常数。与这类曲线相关联的是一种几何乘法定律给定这条曲线上任意两点A和B，然后作直线连接它们（如图）。因为这条曲线的方程是三次的，此直线与曲线必有第三个交点。然后将这个点的y坐标乘上-1，由子方程中y2不变，所得到的对称点仍在此曲线上。我们称它为原先两点的“乘积”AB。令人惊奇的是这个乘法恰好服从适当的代数定律：此曲线上的点用这个乘法形成一个群。
在伦斯特拉的算法中，坐标x和y的值均被模N化了，这里N是我们所要分解的数。如果仅用到一条椭圆曲线，此方法很像波拉德方法。然而，出现在波拉德方法中的数p-1被p-t代替了，这里t依赖于椭圆曲线的选择，不同的曲线给出不同的t，所以可能有一大批p-t。只要其中有一个具有小的除数，这个方法就能找到因子。
因此，这个算法首先是选择某个椭圆曲线并用推广了的波拉德方法寻找一个因子，如果这一步失败了，它能做原来的波拉德方法所做不到的事：试用另一条椭圆曲线。只要在p的邻近有一个相当稠密其元素是小素数的乘积的数集，这个方法将会迅速地找到一个因子。计算精确的运转时间是相当复杂的，其证明依赖于关于上述密度的一个似真但未证明的猜想。其他已知方法也有一个类似的猜测的运转时间，但是它们缺乏伦斯特拉方法的一个重要特征：运转时间依赖子数N的素因子的大小。
直到最近还没有人预见到在椭圆形曲线与分解素因子之间会有任何联系。仅在事后这种联系才弄清楚了，虽然伦斯特拉方法看起来很复杂，它是波拉德方法的自然推广。也许更有效的本原测试方法意想不到地潜在于数论学家的发现之中。如果是这样，某些深奥的，抽象的数学将呈现出新的实际的面貌。那些正在用算法分解因子的计算机科学家们将被奉劝去重新学习数论课程。
[Nature，1987年1月]