新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     >>W3CHINA.ORG讨论区<<     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL → 计算机理论与工程 → 『 算法理论与分析 』 → 求因式分解的算法 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 7411 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 求因式分解的算法 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     whz2xwj 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2005/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给whz2xwj发送一个短消息 把whz2xwj加入好友 查看whz2xwj的个人资料 搜索whz2xwj在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看whz2xwj的博客楼主
    发贴心情 求因式分解的算法

    求因式分解的算法，谢谢各位大虾！！

       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 19:22:00
     
     mysword 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：22
      积分：158
      门派：XML.ORG.CN
      注册：2005/3/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mysword发送一个短消息 把mysword加入好友 查看mysword的个人资料 搜索mysword在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看mysword的博客第2楼
    发贴心情 
    在哪个域里分解？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 19:54:00
     
     whz2xwj 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2005/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给whz2xwj发送一个短消息 把whz2xwj加入好友 查看whz2xwj的个人资料 搜索whz2xwj在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看whz2xwj的博客第3楼
    发贴心情 
    只要1元的就可以了
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 20:31:00
     
     whz2xwj 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2005/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给whz2xwj发送一个短消息 把whz2xwj加入好友 查看whz2xwj的个人资料 搜索whz2xwj在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看whz2xwj的博客第4楼
    发贴心情 
    最高次不超过20，系数范围-1000到1000
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 20:32:00
     
     whz2xwj 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：66
      门派：XML.ORG.CN
      注册：2005/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给whz2xwj发送一个短消息 把whz2xwj加入好友 查看whz2xwj的个人资料 搜索whz2xwj在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看whz2xwj的博客第5楼
    发贴心情 
    求因式分解的算法，谢谢各位大虾！！
    只要1元的就可以了
    最高次不超过20，系数范围-1000到1000
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 20:36:00
     
     asadafag 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：56
      积分：483
      门派：XML.ORG.CN
      注册：2005/3/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给asadafag发送一个短消息 把asadafag加入好友 查看asadafag的个人资料 搜索asadafag在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看asadafag的博客第6楼
    发贴心情 
    ……
    2楼的问题才是关键吧。实数域、复数域、有限域？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/8 20:43:00
     
     bsj731 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：54
      门派：XML.ORG.CN
      注册：2005/9/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给bsj731发送一个短消息 把bsj731加入好友 查看bsj731的个人资料 搜索bsj731在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看bsj731的博客第7楼
    发贴心情 
    请问有限域的怎么求
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/9/6 10:33:00
     
     galois 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：6
      积分：79
      门派：XML.ORG.CN
      注册：2005/10/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给galois发送一个短消息 把galois加入好友 查看galois的个人资料 搜索galois在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看galois的博客第8楼
    发贴心情 
    谈一下我所知道的有关结论吧。
    显然，我们这里谈论多项式因式分解，指的是有理整数Z(也可推广到代数整数，那就更没什么人知道怎么做了)上的多项式因式分解，或是有限域GF(p)上的多项式因式分解。Q上的分解跟Z上等价。 R和C上的分解属于数值计算的范畴，计算机科学家不关心。

    问题一：在GF(p)上求多项式的根。据我所知，目前没找到确定性多项式算法，但有很多随机多项式算法。目前猜测，如果此多项式有可交换的Galois群，那可以在多项式时间分解。
    问题二：在GF(p)上分解多项式。同样，这不会比问题一容易。目前有很多随机多项式算法或是实际性能不错的方法。
    问题三：在Z上分解多项式。有趣的是，这个问题要比Z上的大整数分解容易得多（因此基于多项式分解的RSA体制是没用处的。）。1982年由Lenstra,A.K.，Lenstra.Jr.H.W.和Lovasz,L.提出的著名的LLL算法证明这个问题是属于P类。证明了其复杂性为O(n^12+n^9(log|f|^3)),n为f的次数。但由于它确实很慢，实际上从没有人真正用它来分解因式。

    在GF(p)上，一个比较实用的算法如下：
    设输入多项式为A.
    1.[Squarefree Factorization] 将A变换成A1*(A2^2)*(A3^3)……。A1,A2……都无平方因子，且互素。
    2.[Distinct degree factorization] 对步骤1中算出的每个Ai，找出A(i.d)——A的所有d次素因子的乘积。
    3.[Final splittings] 将A(i,d)分解为多个d次因子。
    4.[Cleanup]

    在Z上，可以借助前面算法去设计一些方法，还是比较复杂。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/10/13 21:55:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2026/4/14 8:57:46

    本主题贴数8，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 93.750ms