能否快速确定素因子，大数分解

wsc810

有一批已知的素数$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$


                  
              
                                                   

mathematica

这类问题很难,不建议研究

kte

想到一个办法,就是将它的可能因子范围划分为n个区间，对每个区间都用$Q_i$进行筛选，而这种筛法可以同时分给每个人去做，怎么想想这就是是试除法