第３６卷第２期 南昌大学学报（工科版） Ｖｏ１．３６ Ｎｏ．２ ２０１４年６月 Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｃｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｅｎ￣ｎｅｅＨｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ） Ｊｕｎ．２０１４ 文章编号：１００６—０４５６（２０１４）０２—０１７９—０３ 一种迭代求解离散对数的Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法 胡建军 （兰州文理学院电子信息工程学院，甘肃兰州７３００１０） 摘要：针对Ｐｏｈｌｉｇ・Ｈｅｌｌｍａｎ类算法中需要存储每一个基数下的同余数的不足，提出一种利用迭代法直接计算离 散对数的方法。该方法不再需要对每一个基数下的同余数进行存储，节约了一定存储空间。同时，利用穷尽搜索 法代替Ｓｈａｎｋ算法的调用，时间复杂度有所降低。理论研究和数字分析表明，改进算法具有较好的计算能力。 关键词：混合基数表示；离散对数；素因子分解；复杂度；循环群 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ Ａｎ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄ ｏｎ Ｐｏｈｌｉｇ－Ｈｅｌｌｍａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔ０ ｒ ｃｏｍｐｕｔ￣ｐｕｔｉｎｇ ｄｉｓｃｒｅｔｅ’ｎｇ ａｌｓｃｒｅｔｅ ｌｏｇａｒｉｔｌｔｈｍ ＨＵ Ｊｉａｎｊｕｎ （Ｅｎｇｉｎｅｅｎｎｇ Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃ＆Ｉｎｆｏｒｍａｔｉｏｎ，Ｌａｎｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｒｔｓ ａｎｄ Ｓｃｉｅｎｃｅ，Ｌａｎｚｈｏｕ ７３００１０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｅｃａｕｓｅ Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ ｃｌａｓｓ ａｌｇｏｒｉｔｈｍｓ ｎｅｅｄ ｓｏｍｅ ｍｅｍｏｒｙ ｆｏｒ ｓｔｏｒｉｎｇ ｅａｃｈ ｒａｄｉｘ ｏｆ ｍｏｄｕｌｕｓ ｏｆ ｃｏｎｇｒｕｅｎｃｅ，ａｎ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄ ｗａｓ ｃａｒｒｉｅｄ ｏｕｔ ｄｉｒｅｃｔｌｙ ｔｏ ｃｏｍｐｕｔｅ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ．Ｔｈｅ ｍｅｔｈｏｄ ｗａｓ ｎｏ ｌｏｎｇｅｒ ｎｅｅｄｅｄ ｗｉｔｈ ｓｔｏｒｉｎｇ ｅａｃｈ ｒａｄｉｘ ｏｆ ｍｏｄｕｌｕｓ ｏｆ ｃｏｎｇｒｕｅｎｃｅ，ｗｈｉｃｈ ｗａｓ ｓａｖｉｎｇ ｓｏｍｅ ｍｅｍｏｒｙ．Ｔｈｅ ｅｘｈａｕｓｔｉｖｅ ｓｅａｒｃｈ ａｌ— ｇｏｒｉｔｈｍ ｗａｓ ａｌｓｏ ａｐｐｌｉｅｄ ｆｏｒ ｅｓｃａｐｉｎｇ ｔｏ ｃａｌｌ Ｓｈａｎｋ ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ．Ｔｈｒｏｕｇｈ ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｉｓ ａｎｄ ｅｘａｍｐｌｅ ｖｅｒｉｉｆｃａｔｉｏｎ，ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｗａｓ ｏｆ ｈｉｇｈ ｃｏｍｐｕｔｉｎｇ ｐｏｗｅｒ． Ｋｅｙ Ｗｏｒｄｓ：ｍｉｘｅｄ ｒａｄｉｘ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ；ｆａｃｔｏｒｉｚａｔｉｏｎ；ｃｏｍｐｌｅｘｉｔｙ；ｃｙｃｌｉｃ ｇｒｏｕｐ 文献［１］是Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法＿２ 的一种改进， 想是：首先，对ｎ进行素因子分解，即ｎ＝Ｐ Ｐ … 尽管文献［１］算法的时间复杂度与Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ Ｐ 。其次，假设ｔ。，ｔ ，ｔ ，…是一个大于１的素数序 算法相同，但是该算法不需要中国剩余定理，节约了 列，则考虑如下的序列： 一定的运行时间。然而文献［１］算法需要一定的存 ｔｏ … ｔ ｌ一１ Ｐｌ 储空间来保存每一个基数上计算的一些同余数。研 ｅ－ …＝ｔｅ究发现，可以利用迭代法直接计算离散对数，能够节 ｔ＋ｅ２－１ ｐ （１） 约一定的存储空间。文献［３］利用穷尽搜索法消除 了Ｓｈａｎｋ算法的调用，当ｎ的素因子是光滑的且光 ｔＨ＋ｌ … ｔｕ一 ，ｌ Ｐ， 滑界较小时，文献［３］的算法比较有效。为此，本文 从而有几＝ｔｏｔｌｆ２…ｔ 一 ，其中Ｍ＝∑ ｔ ，对于 利用迭代法和文献［３］方法对Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ算法 任意的整数 ，０≤ ≤ｎ一１，有下面的表达式成立： 进行了改进。分析表明，改进算法是有效和可行的。 ＝ ＋ｚ１ｔｏ＋Ｚ２ｔｏｔｌ＋Ｚ３ｔｏｔｌｔ２＋…＋ｚ“ｌｔｏｔｔ‘¨ｔｕ一２ １文献［１］算法概述 （２） 其中：系数 ，满足０≤ｚ，≤￡卜１。 设Ｐ是～个大素数，ｎ＝ｐ一１是循环群Ｇ的阶， 因此，Ｙ＝ｇＸ＝ “ “ 。。“ 一 ，则 Ｏｄ， ∈Ｇ，Ｏ／是群Ｇ的生成元，求 ＝ｌｏｇ 。算法的思 Ｙ ＝（ｇ∥‘。ｚ０ｇ“‘ ＋ｚ２ｔＩ＋Ｚ３ｔｌｔ２＋．．．＋Ｚｕ＿ｌｔｌ＂＇ｔｕ＿２）毫（ｇ ｚ０ 收稿日期：２０１３—１２—０９。 基金项目：甘肃省高等学校研究生导师科研资助项目（１１１３－０２）。 作者简介：胡建军（１９７１一），男，副教授。 引文格式：胡建军．一种迭代求解离散对数的Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法［Ｊ］．南昌大学学报：工科版，２０１４，３６（２）：１７９—１８１， １９４． 南昌大学学报（工科版） ｏｒｏｄｐ。调用Ｓｈａｎｋ算法获得ｚ。的值，并保存ｚ。。 由于（Ｙｇ一铀） ＝（ｇ ’） ｇ ‘宅 ≈ ＋‘一 气 一 一 ’ ；（ｇ ） ｍｏｄ Ｐ，因此调用Ｓｈａｎｋ算法获得ｚ 的 值，并保存 。。重复该过程，直到获得 一 。最后获得 ＝Ｚ０＋Ｚ１ｔｏ＋Ｚ２ｔｏｔｌ＋Ｚ３ｔｏｔｌｔｚ＋…＋ ｕ一１ｔｏｔ１…ｔｕ一２。 ２ 迭代求解算法 ２．１．算法思想 假设ｓ ｚ０＋Ｚ１ｔ０＋Ｚｚｔ０ｔ１＋Ｚ３ｔ０ｔ１ｔ２＋…＋ Ｚｋｌｔ。ｔ …ｔ 是前｜ｉ｝个同余系数乘积的和，其中０≤Ｊｊ｝ ＜“一１，则前．ｉ｝＋１个同余系数乘积和的迭代公式为 ｓ川＝ｓ ＋ｚｋｔ０ｔｌ…ｔ 。由式（１）和式（２）可得 ｉ ｚ０（ｒｏｏｄ ｔ０） 一 ｚ－ （ｍ。 ） （３） 一ｓ ２三Ｚ一ｕ－Ｉｔｏｔ１…ｔⅡ一２（ｒｏｏｄ ｔｕ一１） 从式（３）可以看出， 由 兰Ｚ０（ｒｏｏｄ ｔｏ）计算 出，ｚｌ由 —ｚ０；ｚｌｔｏ（ｒｏｏｄ ｔ１）计算出，如此重复，最 后 一ｌ由 一ｓ 塞 一】ｔｏｔｌ…ｔ （ｒｏｏｄ ｔ ）计算得 到， ≥２，即 Ｅ ｓ 一２＋Ｚｕ－Ｉｔ０ｔｌ…ｔ 一１（ｍｏｄ ｔ 一１）。从 整个计算过程来看，算法是一种迭代求和计算，因此 算法不需要保存每一个同余数的值，这样可以节约 ＝∑ 个整数存储空间。 ２．２ 算法实现 输入：阶为凡的循环群Ｇ的一个生成元 ，一个 元素 ∈Ｇ。 输出：离散对数 ＝ｌｏｇ￣Ｂ ｒｏｏｄ Ｐ。 算法如下： 几 ｐｌ“Ｐ２ ・‘ ｒ ； ０＝…＝ｔ １一ｌ Ｐ１，ｔｅ１＝… ｔｅ１＋ｅ２－ｌ Ｐ２，…，ｔｕ ｅ＋ｌ … ｔｕ＿１ Ｐ＂Ｍ ２２ ’一 ｅｉ， Ｉ＝ｌ ｓ：０，ｙ＝ 一ｒｏｏｄ Ｐ，ｔ一１＝１，６：１，叼 １ ｆｏｒ ｉ＝０ ｔｏ ｕ一１ ｛ ＝６ｔ ， 叼 一１，ｉｆ ｔ ＜＞ｔ —ｌｔｈｅｎ仅＝ｏ／ｎ，／ｔ ｍｏｄｐ，Ｙ＝ｙ ｍｏｄＰ， ＝（ ）椰ｒｏｏｄＰ ｆｏｒ ｚｉ＝０ ｔｏ ｔ 一１｛ｉｆ（ ） ｒｏｏｄ Ｐ＝ ｔｈｅｎ ｓ＝ ｓ＋ｚ ，ｅｘｉｔ｝ ｝ Ｒｅｔｕｒｎ ５ ２．３ 算法正确性分析 首先看求解 。由于 ＝ 幻 一 ‘ｍｏｄ Ｐ，ｙ＝ —ｒｏｏｄＰ，ｓ＝０，又由Ｆｅ瑚ａｔ小定理可知， 。 ＝ （ ｌｆ０ ‘ ｌ ‘‘ ） ‘０ ＝ （ ）加（ 龟ｑ＋‘‘。＋ ＿２ｑ … ＿２）“三（ ｎ／‘０）如ｍｏｄ Ｐ。 令 ＝（０ｆ ）ｚ０ ｒｏｏｄＰ，ｂ＝卢 ｍｏｄＰ，则Ｚ０＝ ｌｏｇ。ｂ ｍｏｄ Ｐ。从而ｓ＝Ｚｏ＋ｓ：Ｚ０。 其次看求解 。 同理（ ） “’ ＝ （ａ ｌ‘０ ｌ ｌ ） （ １） ＝ （ ｎ／‘ ） （ 宅 ‘ 。－２ … “一 ）“兰（ａ ‘） ｍｏｄ Ｐ。 令口＝（ “） ｒｏｏｄＰ，ｂ＝（ 一码） ｏｒｏｄＰ， 则ｚ】＝ｌｏｇ ｂ ｒｏｏｄ Ｐ，从而ｓ＝ｓ＋＝】ｔｏ：ｚｏ＋ｚｌｔｏ。 最后，假设前ｌｊ｝个同余系数乘积的和已计算出， 即ｓ ＝ ０＋Ｚ，Ｉｔｏ＋ｚ２ｔ０ｔ１＋ｚ３ｔ０ｔｌｔ２＋…＋Ｚｋ－Ｉｔ０ｔ１…ｔ 一２， 则第．ｉ｝＋１个的值计算方法如下： 因 （ ） ‘。 ） ＝ （ ０ｃｒ ） ‘ Ｏｉｌ＂＂ｔ ＝ （ ｎ／ ） （ ＋１＋’‘’＋ 一２“＋１… ＿２） 兰（ＯＬ ）血ｍｏｄ Ｐ。 令０＝（ “）靠ｒｏｏｄ Ｐ，ｂ＝（卢ｙ ） ‘ ｍｏｄ Ｐ，则 ＝ｌｏｇ ｂ ｍｏｄ Ｐ。 从而ｓ＝ｓ＋ｚｋｔ０ｔｌ…ｔ 一１＝ ０＋Ｚ１ｔ０＋…＋ Ｚ￣ｔｏｔｌ…ｔｋ一１。 如此重复，直至 一１，最终可以求出离散对数 的值，因此，算法是正确的。 ２．４ 数字例子 假设Ｇ＝ 是有限域 ，的循环群，阶ｎ＝７２ ＝２。３ 且生成元ｇ＝５，则Ｍ＝∑ｅｉ＝２＋３＝５， 整数序列为 ０，ｉｌ，ｉ２， ３，ｉ４，ｔ０：ｔｌ＝ｔ２＝２，ｔ３＝ｔ４＝ ３。求解卢＝７的离散对数，即 ＝ｌｏｇ ７ ｒｏｏｄＰ，这里 Ｐ＝７３。 令 ：０，ｔ一１＝１， ＝１，叼＝１，并计算 ＝ ５ （ｍｏｄ ７３）＝４４，则５次循环的计算过程如下： １） ＝６ｔ０＝２；１７＝叼￡一ｌ：１；由于ｔ０＝２≠ｔ一１ ＝１，所以ａ＝ｇ “ｒｏｏｄ Ｐ＝７２；ｙ＝ ｒｏｏｄ Ｐ＝１， ＝（Ｂｙ） ｍｏｄ Ｐ＝７２； 从１到０循环，因为当Ｊ＝１ 时，（ ） ｒｏｏｄ Ｐ＝万，所以 ： ＋Ｊｎ＝０＋１＝１。 ２） ＝艿￡Ｉ＝４；叩＝ ｚ０＝２；由于ｔｌ＝２＝ｔ０＝ ２，所以 ＝７２所以保持不变；），＝ ｒｏｏｄ Ｐ＝４４， ＝（ ） ｒｏｏｄ Ｐ＝１ 从１到０循环，因为当Ｊ＝０ 时，（ ） ｒｏｏｄ Ｐ＝ ，所以 ＝ ＋Ｊｎ＝１＋０＝１。 ３） ＝６ｔ２＝８； ＝ ｌ＝４；由于ｔ２＝２＝ｔＩ＝ ２，所以 ＝７２所以保持不变；ｙ＝ ｒｏｏｄ Ｐ＝４４， ：（ ） ｒｏｏｄ Ｐ＝１ 从１到０循环，因为当Ｊ＝０ 时，（ ） ｍｏｄ Ｐ＝卢，所以 ： ＋－，叼＝１＋０：１。 ４）６＝６ｔ３＝２４； ＝叼 ２＝８；由于ｔ３：３≠ｔ２ ＝２，所以 ＝ｇ “ｍｏｄ Ｐ：８；，，＝ ｒｏｏｄ Ｐ＝４４，声 第２期 胡建军：一种迭代求解离散对数的Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法 ＝（／３ｙ） ｒｏｏｄ Ｐ＝８； 从２到０循环，因为当 ＝１ 时，（ ） ｍｏｄ Ｐ＝ ，所以 ＝ ＋ ＝１＋１×８＝ ９。 ５）６＝６ｔ４：７２；叼＝ｒ／ｔ３＝２４；由于ｔ４＝３＝ｔ３ ＝３，所以 ：８保持不变；ｙ＝ ｍｏｄ Ｐ＝２２，万＝ （ ） ｍｏｄＰ：８√从２到０循环，因为当 ＝１时， （ ） ｍｏｄ Ｐ＝ ，所以 ： ＋ｊｖ＝９＋ｌ×２４：３３。 即 ＝３３为所求结果，亦即ｌｏｇ５７ ｒｏｏｄ Ｐ＝３３。 验证可知５ ３３ｏｒｏｄ ７３＝７，所以算法是正确和有 效的。 以上计算过程没有保存每一次循环中满足等式 的 值，而是利用迭代法直接求出了离散对数的值， 节省了存储空间。 ３ 算法分析 ３．１算法复杂性分析 由于本文利用了文献［３］的方法计算离散对 数，因此算法的时间复杂性与文献［３］一致，即 Ｄ（∑ｅ‘＝１ ｉｐｉ）。 文献［１］的时问复杂性为 ０（∑ｅ （１ｏｇ ｎ＋ ｌ０ｇ Ｐ ）） ，￣Ｎ［３ ３证明了 不等式（４）成立 Ｄ（∑ｅｉｐ ）＜Ｄ（∑ｅ （１ｏｇ ｎ＋ ｌ０ｇ：Ｐ ）） ‘ １ ‘ ｌ （４） 这表明，改进算法在时间复杂性上要优于文 献［１］。 但是文献［３］并未给出时间复杂性的下界。假 设ｑ是ｎ的最大素因子，则文献［６］指出，基于 Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ算法所有可能的编码函数所需的最 小运行时间为 （１ｏｇ： ） ¨。在这一事实的基础 上，其他基于Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ类似算法的时间复杂 性也不会小于该下界 ，因此Ｄ（∑ｅｉｐ ）的时间 复杂性满足不等式（５） Ｄ（ ｌｏｇ ｎ）≤Ｄ（∑ｅｉｐ ） （５） 在空间复杂性上，因为ｎ的互素数为ｒ，前后素 数要有区分，因此本文算法的存储复杂度为Ｏ（２ｒ）。 其他空间复杂度可以忽略不计。 ３．２ 与文献［１］算法的比较 从３．１分析表明，本文算法在空间和时间复杂 性方面都要优于文献［１］，为了验证３．１的结论，以 ２．４的数字例子为例，下面分别从时间复杂度和空 间复杂度２个方面进行比较，见表１和表２。 表１ 时间复杂度比较 Ｔａｂ．１ Ｃｏｍｐｌｅｘｉｔｙ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｉｍｅ 表２ 空间复杂度比较 Ｔａｂ．２ Ｃｏｍｐｌｅｘｉｔｙ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｔｏｒｅ 从表１可以看出：利用公式计算，文献［１］群乘 法运算次数大约是本文的３．５倍；从实际群乘法运 算次数来看，文献［１］（包括实际和构造表的群乘法 次数）大约是本文的１．６７倍，文献［１］算法所需的 查询、整理表的次数分别为５、１４，而本文均为０。 因为［ ｌｏｇ ｎ］＝［，／３＇－ｌｏｇ２７２］：１１，∑ｅｉｐ ＝ ＝ｌ １２，即 ｌｏｇ２７２＜２×３＋３×２，这说明当 的素因子 是光滑的且光滑界较小时，２个值相当，所以本文算 法有效。 从表２可以看出：文献［１］和本文算法在素因 子存储上所占的空间相同，但是在群元素存储和同 余数存储２项上，文献［１］所需的存储分别为２和５， 而本文所需存储空间为均为０。 从以上比较可以看出，本文算法明显优于文 献［１］。 ４ 结语 Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ算法属于确定性算法，不存在 盲目性，当阶ｎ的素因子是光滑的且光滑界较小时， Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ算法最快。本文对Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ系 列算法进行了再次改进，除了节省了同余数存储所 需的存储空间外，对指数模运算的计算进行了改进， 分析表明，改进算法要明显优于文献［１］的算法，同 时指出了文献［３］算法的理论下界。然而，本文算法 并没有给出：理论上，改进算法比文献［１］在时间复 杂性上究竟快多少，时间复杂度的确切上界是否存 在更为确切的值。另外，数字验证发现，文献［３］所 给的数字例子的时间复杂度比文献［６］所给的公式 下界还要小（１７＜２４），这表明， （下转第１９４页） ・１９４・ Ｉｌ 二 １Ｊ １Ｊ南昌大学学报（工科版） ２ １Ｊ２０１４年 １Ｊ３ １Ｊ４ １Ｊ５ １Ｊ６ ７ 大小主要根据经验设置，过大则退化为普通区域水 平集方法，可能导致精度下降，过小则导致运算时间 增大。 ｔｅｘｔｕｒｅ，ｍｏｔｉｏｎ ａｎｄ ｓｈａｐｅ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００７，７２（２）：１９５—２１５． ［８］ ＣＨＡＮ Ｔ，ＶＥＳＥ Ｌ．Ａｃｔｉｖｅ ｃｏｎｔｏｕｒｓ ｗｉｔｈｏｕｔ ｅｄｇｅｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ Ｏｎ Ｉｍａｇ Ｐｒｏｃ，２００１，１０（２）：２６６—２７７． 参考文献： 姜玉新，张运．超声医学高级教程［Ｍ］．北京：人民军 医出版社，２０１２． 黄剑华，于瀛星，张英涛，等．基于一致性直方图的超 声乳腺图片分割方法［Ｊ］．哈尔滨工业大学学报， ２００８，４０（７）：１１０３—１１０６． ［９］ ＬＩ Ｃ Ｍ，ＫＡＯ Ｃ Ｙ，ＧＯＲＥ Ｊ Ｃ，ｅｔ ａ１．Ｍｉｎｉｍｉｚａｔｉｏｎ ｏｆ ｒｅ． ｇｉｏｎ・ｓｃａｌａｂｌｅ ｆｉｔｔｉｎｇ ｅｎｅｒｙ ｆｇｏｒ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，２００８，１７（２）： １９４０—１９４９． ａ１．Ａ ｇｅｏｍｅｔｒｉｃ ［１０］ ＣＡＳＥＬＬＥＳ Ｖ，ＣＡＴＦＥ Ｆ，ＣＯＬＬ Ｔ，ｅｔｍｏｄｅｌ ｆｏｒ ａｃｔｉｖｅ ｃｏｎｔｏｕｒｓ ｉｎ ｉｍａｇｅ—ｐｒｏｃｅｓｓｉｎｇ［Ｊ］．Ｎｕｍｅｒ－ ｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ，１９９３，６６（１）：１—３１． ＬＩ Ｃ，ＨＵＡＮＧ Ｒ，ＤＩＮＧ Ｚ，ｅｔ ａ１．Ａ ｌｅｖｅｌ ｓｅｔ ｍｅｔｈｏｄ ｆｏｒ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｎ ｔｈｅ ｐｒｅｓｅｎｃｅ ｏｆ ｉｎｔｅｎｓｉｔｙ ｉｎｈｏｍｏｇｅ・ 沈嘉琳．基于灰度阈值分割和动态规划的超声图像乳 腺肿瘤边缘提取［Ｊ］．航天医学与医学工程，２００５，１８ （４）：２８１～２８４． 刘红，张欣，吕丹，等．超声乳腺肿瘤图像的自动分割 ［Ｊ］．计算机工程与设计，２０１０，３１（１５）：３５３７—３５３８． 聂敏，高满屯．基于活动轮廓模型的Ｂ超乳腺肿瘤图 ｎｅｉｔｉｅｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ＭＲＩ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，２０１１，２０（７）：２００７—２０１６． ｖｅ ｃｏｎｔｏｕｒｓ ［１２］ ＺＨＡＮＧ Ｋ Ｈ，ＳＯＮＧ Ｈ Ｈ，ＺＨＡＮＧ Ｌ．Ａｃｔｉ像分割［Ｊ］．北京生物医学工程，２００８，２７（５）：５３４— ５３５，５５２． ＬＩＵ Ｂ，ＣＨＥＮＧ Ｈ Ｄ，ＨＡＮＧ Ｈ Ｌ，ｅｔ ａ１．Ａｕｔｏｍａｔｅｄ ｓｅｇ— ｍｅｎｔａｔｉｏｎ ｏｆ ｕｈｒａｓｏｎｉｃ ｂｒｅａｓｔ ｌｅｓｉｏｎｓ ｕｓｉｎｇ ｓｔａｔｉｓｔｉｃａｌ ｔｅｘ— ｔｕｒｅ ｃｌａｓｓｉｉｃａｔｉｆｏｎ ａｎｄ ａｃｔｉｖｅ ｃｏｎｔｏｕｒ ｂａｓｅｄ ｏｎ ｐｒｏｂａｂｉｌｉｔｙ ｄｒｉｖｅｎ ｂｙ ｌｏｃａｌ ｉｍａｇｅ ｆｉｔｔｉｎｇ ｅｎｅｒｙ［Ｊ］．Ｐａｔｇｔｅｒｎ Ｒｅｃｏｇｎｉ— ｔｉｏｎ，２０１０，４３（４）：１１９９—１２０６． ａ１．Ｌｅｖｅｌ ｓｅｔ ｅｖｏｌｕｔｉｏｎ ［１３］ ＷＡＮＧ Ｙ，ＷＡＮＧ Ｌ，ＸＩＡＮＧ Ｓ，ｅｔｗｉｔｈ ｌｏｃａｌｌｙ ｌｉｎｅａｒ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｆｏｒ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓ－ ｉｎｇ．Ｂｒｕｓｓｅｌｓ，Ｂｅｌｇｉｕｍ，２０１ １：３４２２—３４２５． ｄｉｓｔａｎｃｅ［Ｊ］．Ｕｈｒａｓｏｕｎｄ ｉｎ Ｍｅｄｉｃｉｎｅ ａｎｄ Ｂｉｏｌｏｇｙ，２００８， ３５（８）：１３０９—１３２４． ＤＡＮＩＥＬ Ｃ，ＭＩＫＡＥＬ Ｒ，ＲＡＣＨＩＤ Ｄ．Ａ ｒｅｖｉｅｗ ｏｆ ｓｔａｔｉｓｔｉ－ ｃａｌ ａｐｐｒｏａｃｈｅｓ ｔｏ ｌｅｖｅｌ ｓｅｔ ｓｅｇｍｅｎｔａｔｉｏｎ：ｉｎｔｅｇｒａｔｉｏｎ ｃｏｌｏｒ， ［１４］ ＷＩＬＬＩＡＭ Ｋ Ｐ．数字图像处理［Ｍ］．邓鲁华，延恒，等 译．北京：机械工业出版社，２００５． （上接第１８１页） 随着Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ系列算法的进一步研究， Ｐｏｈｌｉｇ．Ｈｅｌｌｍａｎ系列算法的时间复杂度还可以进一 步降低。因此这需要今后做更为深入的探讨。 师范大学自然科学学报，２０１３，３６（５）：ｌ９—２２． ［４］ 周玉洁，冯登国．公开密钥密码算法及其快速实现 ［Ｍ］．北京：国防工业出版社，２００２． ［５］ 肖攸安．椭圆曲线密码体系研究［Ｍ］．武汉：华中科技 大学出版社，２００６． ［６］ ＳＨＯＵＰ Ｖ．Ｌｏｗｅｒ ｂｏｕｎｄｓ ｆｏｒ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ ａｎｄ ｒｅｌａｔ— 参考文献： ＴＨＩＯＮＧ Ｊ Ａ．Ａ ｓｅｒｉａｌ ｖｅｒｓｉｏｎ ｏｆ ｔｈｅ Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ ａｌｇｏ— ｒｉｔｈｍ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ［Ｊ］．ＡＡＥＣＣ， １９９３，４（１）：７７—８Ｏ， ｌｇｏｒｉｔｈｍ ｆｏｒ ［２］ ＰＯＨＬＩＧ Ｓ Ｃ，ＨＥＬＬＭＡＮ Ｍ Ｅ．Ａｎ ｉｍｐｒｏｖｅｄ ａｅｄ ｐｒｏｂｌｅｍｓ［Ｃ］／／Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐ ｔｏｌｏｇｙ—Ｅｕｒｏｃｒｙｐｔ’ ９７，Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｖｏｌｕｍｅ １２３３． Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ，１９９７：２５６—２６６． ｃｏｍｐｕｔｉｎｇ ｌｏｇａｉｒｔｈｍｓ ｏｖｅｒ ＧＦ（Ｐ）ａｎｄ ｉｔｓ ｃｒｙｐｔｏｇｒａｐｈｉｃ ［７］ ［８］ ＳＴＥＩＮ Ａ，ＴＥＳＫＥ Ｅ．Ｏｐｔｉｍｉｚｅｄ ｂａｂｙ ｓｔｅｐ—ｇｉａｎｔ ｓｔｅｐ ｍｅｔｈ— ｓｉｇｎｉｉｆｃａｎｃｅ［Ｊ］．ＩＥＥＥ Ｉｎｆｏ Ｔｈｅｏ Ｓｏｃ，１９７８，２４（１）：１０６ —ｏｄｓ［Ｊ］．Ｊ Ｒａｍａｎｕｊａｎ Ｍａｔｈ Ｓｏｃ，２００５，２０（１）：１—３２． ＤＩＥＭ Ｃ．Ｏｎ ｔｈｅ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｐｒｏｂｌｅｍ ｉｎ ｅｌｌｉｐｔｉｃ １ｌ０． ［３］ 胡建军，裴东林．Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法的改进［Ｊ］．湖南 ｃｕｒｖｅｓ［Ｊ］．Ｃｏｍｐｏ Ｍａｔｈ，２０１１，１４７（１）：７５—１０４．
