找回密码
 欢迎注册
查看: 8899|回复: 4

[求助] 能否快速确定素因子,大数分解

[复制链接]
发表于 2017-4-16 12:15:16 | 显示全部楼层 |阅读模式
悬赏100金币未解决
本帖最后由 wsc810 于 2017-4-16 15:13 编辑

有一批已知的素数$Q_i$,即$Q_0,Q_1,Q_2,...$和未知的单质数$d_j$,但知道对某个$d_j$雅克比符号$(d_j/Q_i)=1$,若给定$d_j$的上限值为$a_0$,有无快速方法求出符合条件的数$d_j$

问题背景

大数分解

假设要分解的数为200位左右的合数$d$,通过连分式的$PQa$算法展开

$P_0=0,Q_0=1$

$p_1=a_0=[\sqrt{d}],Q_1=d-a_0^2$

$a_n=[(P_n+\sqrt{d})/Q_n]$

$P_{n+1}=a_nQ_n-P_n$

$Q_{n+1}=(d-P_{n+1}^2)/Q_n$

求得$Q_n$,另有连分式公式$p_{n-1}^2-dq_{n-1}^2=(-1)^nQ_n=\pmQ_n$

其中$[a_0;a_1,a_2,...,a_n]=p_n/q_n$

所以有$p_{n-1}^2\equiv (-1)^nQ_n(\mod d)$

将$n$代换为$i$,$d_j$为$d$的素因子

因此有

$(\frac{(-1)^iQ_i}{d_j})=1$


当$i$为偶数且$Q_i=4k+1$的素数时

$(d_j/Q_i)(Q_i/d_j)=(-1)^{(d_j-1)/2*(Q_i-1)/2}$

                       $=(-1)^{(d_j-1)k}$

                       $=1$

即                    $(d_j/Q_i)=1$   


当$i$为奇数且$Q_i=4k+3$素数时,$({-Q_i}/d_j)=({-1}/d_j)(Q_i/d_j)$

                                                   $=(d_j/Q_i)(-1)^{(d_j-1)/2}(-1)^{(d_j-1)/2*(Q_i-1)/2}$
                                                   
                                                   $=(d_j/Q_i)(-1)^{(d_j-1)/2*(1+(Q_i-1)/2)}$

                                                   $=(d_j/Q_i)(-1)^{(d_j-1)(k+1)}$

                                                   $=(d_j/Q_i)$

即                $(d_j/Q_i)=1$

因此,对于求得满足条件的$Q_i$并不是难事,而且可以足够多(令$d$等于$k*d$)。关键在于给定上限$\sqrt{d}$, 利用题目中的雅克比符号这一限制条件,是否有快速算法找到其素因子$d_j$


                  
              
                                                   

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-4-17 12:19:38 | 显示全部楼层
这类问题很难,不建议研究
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2019-4-14 15:11:43 | 显示全部楼层
想到一个办法,就是将它的可能因子范围划分为n个区间,对每个区间都用$Q_i$进行筛选,而这种筛法可以同时分给每个人去做,怎么想想这就是是试除法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 15:12 , Processed in 0.057919 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表