l7_numtheory2.pdfVIP

数论 II Alan Turing 的图片因为版权的原因被去除了。 在上面的照片中的人是 Alan Turing， 在计算机科学的历史上最重要的人物。数十年， 他引人入胜的传记由政府必威体育官网网址、社会禁忌， 和甚而他自己的欺骗覆盖了。 在 24岁，Turling写了一篇论文，名字是，“论可计算数---有“Entscheidungsproblem” 的应用 。论文的紧要关头是用一个典雅的使用数学用语的方式塑造了一台计算机。这是突 破， 因为它允许利用数学工具在计算问题上使用。例如， 在他的手中模型， Turing 立刻 证明， 那里存在计算机无法解决的问题— 无论程序员多么天才。Turing论文是更加卓越的， 因为在 1936 年他写了它，在任一台计算机实际上存在的整整 10年之前。 在标题的词 “Entscheidungsproblem”由大卫 Hilbert 在 1900 提出的 28 个数学问题 的当中一个， 这些问题当作是 20 世纪的数学家的挑战。Turing 在同样的论文中解决了一 个。并且或许您已经听说了 “Church-Turing 理论”? 同样的论文。如此 Turing 明显地是 引起许多令人惊讶的想法的一个聪明的人。但这次演讲是大约一个 Turing 的不够吸引人想 法。它设计到代码。它涉及到数论。它有点儿愚笨的。 1 Turing的代码 让我们回到 1937 年的秋天。纳粹德国仍然在 Adolf Hitler 的统治之下，世界范围的 战争迫在眉睫， 和— 像我们— Alan Turing 考虑数理的有用性。他预测了那保存军事秘 密会是重要的，在以后的冲突中，且提出使用数理加密通信方式。这是了由我们自己的时间 决定的想法。今天， 数论是为许多公钥加密系统、数字签名计划、密码散列函数， 和数字 现金系统的依据。每次从亚马孙在您买一本书， 在WebSIS检查您的等级， 或使用 PayPal 帐户时候， 您依靠数论算法。 在构想他的代码以后， Turing 从公视线中消失了， 并且过了半个世纪，世界才知道 它在哪里他做了什么的故事。我们回到 Turing生活一会儿； 暂时， 让我们调查 Turing 留 下的代码。细节是不定的， 因为他从未正式出版了想法， 如此我们要考虑多个可能性。 1.1 Turing的代码(版本 1.0) 首要的挑战是翻译文本消息成整数，以便我们能在其上进行数学操作。这步不是欲使消 息更加难读， 因此细节不太重要。这有一种方法： 用两个数字替换消息的每个字母(A = 01， B = 02， C = 03， 等。) 并且将所有数字连接起来形成一个巨大的数字。例如， 消息 “victory” 能被翻译这样: PDF 文件使用 pdfFactory Pro 试用版本创建 Turing 的代码要求消息是一个质数， 因此我们也许需要填塞结果以几个更多数字来生成质 数。在这种情况下， 附加数字 13 给出数字 2209032015182513， 它是质数。 现在这里是加密是如何工作。在如下描述中， m是我们要的没有加密的消息(我们也想 把它必威体育官网网址)， m? 是加密的消息(是 Nazis 也许拦截的)， 并且 k 是密钥。 前期 发令者和接收者同意一个秘钥， 是一个大质数 k 。 加密 通过计算消息 m: m? = mk 解密 接收器解码 m? 由计算: 例如， 假设， 秘钥是质数 k = 22801763489 并且消息 m 是 “victory”。然后加密后的消 息是: 你也许自然地询问 Turing代码的一些问题。 1.发送者和接收者怎么可能保证 m 和 k 质数， 按照要求? 确定是否一个大数字是质数或合数的一般问题已经被学习了几个世纪， 并且合理 的好的质数测试在 Turing的时代就闻名了。2002 年， Manindra Agrawal， Neeraj Kayal， 和 Nitin Saxena宣布了保证数字 n 上工作的质数测试在(logn)12 步内。这明确地安置了 质数测试在类 “容易” 计算问题最后。令人惊讶地， 他们的突破算法的描述长度只 是十三行! 2.是 Turing的代码安全吗? 纳粹仅仅看到唯一被编成密码的消息 m? = m·k， 如此恢复原始的消息 m 要求分解 m?。尽管巨大努力， 真正地高效率的析因的算法曾经未被发现。看起来是一个根本上困难 的问题， 虽然突破某天不是不可能的。实际上，用他的发现，在计算能力上有上限， Turing 代码投入对实用用途。因而， 假设 m 和 k 是充足地大的，纳粹似乎是没有运气! PDF 文件使用 pdfFactory Pro