在 GT3 上用二次筛选法分解大数字

文档选项 未显示需要 JavaScript 的文档选项

级别： 初级

Vladimir Silva (vsilva@us.ibm.com), OGSA 开发负责人，Advanced Systems Development

2004 年 4 月 01 日

当今大多数安全通信机制，包括 SSL 和加密算法，都基于这样一个简单的事实，即对一个非常大的数字进行因数分解在计算上是十分困难的。我们所谓的“困难”，是指在指定的当前计算资源下，对于一个非常大的数字，要找到它的因数（即它们相乘的结果是原来的数字）可能需要花费几年的时间。在设计来完成这一任务的多种算法之中，二次筛选法的速度最快。本文中，Vladimir Silva 在 Globus Toolkit 3.0 上基于 OGSA 实现了一种网格环境中自初始化的二次筛选法。

当今的计算机系统安全性取决于现代的加密算法，因此严重依赖于有效掌握大数字因数分解的复杂性。二次筛选法（quadratic sieve）提供了目前已知最快的因数分解算法。

本文中，我将告诉您如何用网格计算的事实标准，Globus Toolkit，在分布式环境中实现这一算法。这篇文章详细介绍了如何构建二次筛选的 OGSA 实现，并着重介绍一个独立的因数分解引擎。这个引擎是与 OGSA 兼容的一层，由服务工厂类接口和服务实现组成，还包括一个客户机程序，您可以用它调用给定主机上的 GT3 容器创建的实例。

首先看看二次筛选法的工作原理。

二次筛选法的工作原理

用二次筛选法对一个数字 n 进行因数分解，就是要找到两个数字 x 和 y ，它们模 n 之后不相等，并且 x 和 -y 模 n 之后也不相等，但是 x ² =y ² (mod n) 。如果找到了这两个数字，那么就可以说 ( x+ y) ( x- y) = 0 (mod n) 。因此 x+ y 和 x- y 就一定与 n 具有相同的非平凡因数。

用二次筛选法进行因数分解有赖于是否能够找到一组数字，这组数的因数可以表示为一些预先选择的素数的乘积。然后用幂向量的形式将这些因数记录下来。一旦具备了足够多的向量，就可以构造一个包含线性依赖关系的集合。用这种线性依赖关系就可以找到两个平方后模 n 相等的数字。

为实现这一目标，二次筛选方法使用了一个素数集合，称作因数基（ factor base）。然后，搜索出那些可以完全分解成这个因数基中的素数的数字。如果因数基中有 k 个素数，那么每一个可分解为因数基中素数的数字就存储为一个 k 维的向量，向量 y 中的第 i 个项表示因数基中第 i 个素数在 y 因数分解结果当中的幂。

最后进行筛选操作，找出 f( r) = r ² - n 的那些值，而这些值因数分解的结果完全包含在这个因数基中。然后像 Dixon 因数分解法中那样应用高斯消除法，找出是某数的完全平方的一组 f( r) 。

下表列出了两种最快的因数分解算法

两种最快的因数分解算法的启发式时间复杂度

从这张表中可以看出，数字域筛选法是最快的因数分解算法。它的发明人是 Pollard，主要用于对诸如 RSA-1XX 这样的大数字进行因数分解。这种方法是已知的最强大的一般数字因数分解方法。

二次筛选与数字域筛选 尽管数字域筛选（NFS）在启发式分解方面比 QS 快，而 QS 依然是分解 50 至 110 位数字时的首选方法。从本质上讲，这两种方法都是基于同样的思想，如因数基、平滑、筛选以及查找依赖关系等概念。NFS 是从 QS 所使用的技术发展出来的，而 QS 又对以前的一些算法，如 Dixon 因数分解方法等做了进一步的发展。大多数现代的因数分解技术都将所有这些技术组合起来，以期达到最优的性能。

接下来，我们看看基于 OGSA 的二次筛选法的实现。

回页首

基于 OGSA 的二次筛选算法实现

OGSA 因数分解服务是用三个基本组件实现的：

• 用二次筛选实现的单机版因数分解引擎。
• OGSA 兼容层，由服务工厂接口和服务实现组成。
• 客户机程序，可用来调用由指定主机上的 GT3 容器创建的实例。

下图显示了这些组件之间的关系。

首先看看因数分解引擎。

回页首

因数分解引擎

因数分解引擎可以在单机模式下运行，其中包含用 Java 语言实现的二次筛选算法，代码的基础来自 Dario Alejandro Alpern。为了在单机模式下运行该引擎，可以使用如 清单 1所示的命令。

接下来介绍访问这个因数分解引擎的网格服务接口。

回页首

OGSA 兼容的服务层

要使用我们的 OGSA 服务，首先要创建一个服务接口（ service interface），它定义了可被客户机远程调用的方法。

因数分解服务接口

清单 2生成一个因数分解服务接口。

该方法输入一个大数字，然后将输出信息转储到服务器上的文件上。因为对于大的数字而言，如 RSA-1XX，因数分解的过程可能要持续几个月，因此服务器返回的是用 XML 表示的状态信息。可以通过监视服务器的日志看到实际的处理过程。

服务的实现

服务的实现中包含了实际的代码，无论何时运行一个工厂实例，都会执行这段代码。 清单 3用所需的参数调用了二次筛选因数分解引擎。

创建部署描述符

部署描述符告诉 GT3 到何处去寻找诸如 Schema（WSDL）文件、服务接口以及服务实现之类的服务组件，如 清单 4所示。

创建模式文件和网格档案文件（GAR）

在 GT3 中使用这一服务之前还要进行许多步骤。幸好所有的步骤都可以用 Ant 和 shell 脚本自动实现。在 Factorization/src目录下有两个 shell 脚本，可以自动构建服务。这些脚本要求在 build.properties 文件中包含系统所依赖的信息，如 GT 的安装目录等。您可以对这个文件进行编辑，使之与您的平台保持一致（参阅 清单 5）。

这些 shell 脚本可以创建 WSDL 模式、OGSA 接口桩类，还可以编译所有的文件，将所有的东西都打包到一个 JAR 文件中，然后，创建一个可部署的网格档案文件（GAR）。（有关编写网格服务的深入叙述，请参阅 参考资料一节中列出的 Globus Toolkit programmer's tutorial。）

将服务部署到 GT3 容器中

使用该服务之前的最后一个步骤是将其部署到 GT3 网格服务容器中。 清单 6中所示的命令可以实现这个目的。

一旦服务成功部署，您就可以用服务浏览器 GUI 查看该服务，并创建服务的实例，如图 2 所示。

回页首

服务客户机程序

服务客户机是用于远程调用指定主机上因数分解服务的程序（参阅 清单 7）。

回页首

运行因数分解客户机

客户机程序可以用来实现因数分解，方法是向由特定容器创建的实例发送远程调用请求（如 清单 8所示）。

在运行该命令之前，必须使用那个服务浏览器创建一个因数分解服务的实例。在这个例子中，我们假定实例的名字叫做 FAC。

同时请注意，必须正确设置 OGSA 环境。而且，工厂类必须位于 CLASSPATH 环境变量中。 Factorization目录下提供了一个脚本，可以很方便地利用本地主机上的工厂。例如， test_client FAC 1231232131232132323123123 c:\\temp\\facs.txt 这条命令可以使用本地主机的 GT3 容器中的 FAC 实例对指定数字进行因数分解，并将结果保存在服务器的 c:\temp\facs.txt文件中。

如果您浏览一下源代码，就会发现这个项目是用 Borland JBuilder 和 Apache Ant 等工具开发的。主文件夹称为 Factorization，您可以在其中发现：

1. src：包含源代码和 build XML 文件。
2. classes：包含编译过的 java 代码。

src文件夹下提供了很方便的脚本（Windows 和 Linux 平台），可以创建 GT3 服务的 GAR（grid 档案文件），用于在 Globus 容器中部署。如果要构建这个项目，build.properties 文件必须进行调整，以适应您的操作系统和 Globus 的位置。用客户机测试服务的脚本位于根文件夹下（ test_client.xx）。

回页首

数字分解总结

我已经介绍了一种基于分布式 OGSA 实现的快速二次筛选算法，这可以帮助您越过最初的几个步骤，掌握如何对很大的数字进行因数分解的能力，这一点对于保证当前计算系统中的安全性是一个至关重要的特性。这个算法设计为在 Globus Toolkit 上使用。我们集中于构建一个单机版的因数分解引擎，一个由服务工厂接口和服务实现组成的 OGSA 兼容层，以及一个客户机程序，可以用来调用由 GT3 容器在指定主机上创建的实例。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文.
  
  
• 下载并研究本文中用到的 源代码。
  
  
  
  
• “ GT3 and WebSphere compatibility”一文解决了编写安全的 Web 网格应用时遇到的兼容性问题。
  
  
  
  
• “ Factorization of a 512-bit RSA Modulus”这篇报告记录了密码学的一些历史，作者在报告中讨论了如何用数字域筛选法对 512 位 155 个数字的 RSA-155 进行完整的因数分解；还探讨了 RSA 的相关情况。（PDF）
  
  
  
  
• “ The Quadratic Sieve Factoring Algorithm”一文详细描述了二次筛选算法。
  
  
  
  
• “ Grid Job submission using the Java CoG Kit”（ developerWorks, 2003 年 2 月）一文描述了如何编写基于 Java 的网格应用程序。
  
  
  
  
• “ 使用 Globus Toolkit 监控和发现服务查询网格”（ developerWorks，2003 年 4 月）详细阐述了如何编写基于 Java 的网格查询。
  
  
  
  
• “ 使用监控和发现服务实现网格信息提供程序”（ developerWorks，2003 年 4 月）描述了如何用 Globus Toolkit 发布有关网格资源共享文件的信息。
  
  
  
  
• “ 用 GridFTP 传送文件”（ developerWorks，2003 年 4 月）阐述了如何用 Globus Toolkit 操纵一个简单的 Java 类。
  
  
  
  
• “ 网格安全：前沿技术”（ developerWorks，2003 年 8 月）概要介绍了网格安全方面的前沿消息。
  
  
  
  
• “ 在 Java 技术中使用 Globus 网格安全基础设施”（ developerWorks，2003 年 9 月）解释了如何用 Java CoG Kit 1.1 生成网格凭证。
  
  
  
  
• “ 用 Globus Toolkit 3.0 编写安全的网格服务”（ developerWorks，2003 年 10 月）解释了 Globus Tookiet 3.0 在安全方面的术语和概念，并展示了如何在网格服务中实现消息级的安全性。
  
  
  
  
• 本文的二次筛选算法是基于 Dario Alejandro Alpern 编写的代码实现的；在这个 站点 上他谈论了用筛选法实现因数分解的问题，还提供了一个很好的程序，可以用椭圆曲线法分解因数。
  
  
  
  
• MathWorld 上用一页的篇幅很好地解释了 二次筛选算法。
  
  
  
  
• MathWorld 上用一页的篇幅很好地解释了 数字域筛选算法。
  
  
  
  
• 开发人员希望了解的有关 GT3 的所有信息都可以从 Globus Toolkit 3 Programmer's Tutorial中找到。
  
  
  

关于作者

		Vladimir Silva 出生在厄瓜多尔的基多。他于 1994 年从陆军工学院（Polytechnic Institute of the Army）获得系统分析员（System's Analyst）学位，然后，在中田纳西州立大学（Middle Tennessee State University）获得了他的计算机科学硕士学位。毕业后，他加入了 IBM “WebAhead”技术智囊团。他的兴趣包括网格计算、神经网络、人工智能。他还拥有包括 OCP、MCSD 和 MCP 在内的众多 IT 证书。可以通过 vsilva@us.ibm.com 或者 vladimir_silva@yahoo.com 与 Vladimir 联系。

对本文的评价

太差！ (1) 需提高 (2) 一般；尚可 (3) 好文章 (4) 真棒！(5) 建议？

回页首