数学研发论坛

 找回密码
 欢迎注册
123
返回列表 发新帖
楼主: 无心人

[讨论] 关于伪素数与素性测试的一些事情

[复制链接]
 楼主| 发表于 2021-12-19 15:04:51 | 显示全部楼层
### (二)、Lucas 序列素性测试

若 $P \in \mathbb{Z}+,Q \in \mathbb{Z},D=P^2-4Q$为整数,定义 Lucas 序列 $U,V$:

$U_0=0,U_1=1,\dots,U_{k+2}=PU_{k+1}-QU_k (k \ge 0)$,

$V_0=2,V_1=P,\dots,V_{k+2}=PV_{k+1}-QV_k (k \ge 0)$,

若 $n \in N+$ 是大于 1 的奇数,选择 $D,P,Q$ 满足 Jacobi 符号 $J(\frac{D}{n}) = -1$,

当 $n$ 是素数且 $GCD(n,Q)=1$,我们有:
$$U_{n+1} = 0 (mod\ \ n)\tag{5-1}$$ $$V_{n+1} = 2Q (mod\ \ n)\tag{5-2}$$

另外,如果 $n$ 是奇素数,$\delta(n) = n - J(\frac{D}{n})$,且 $GCD(D, n) = 1$,则:
$$U_{\delta(n)} \equiv 0 (mod\ \ n)\tag{5-3}$$ $$V_{\delta(n)} \equiv 2Q^{(1-J(\frac{D}{n}))/2} (mod\ \ n)\tag{5-4}$$ $$U_n \equiv J(\frac{D}{n}) (mod\ \ n)\tag{5-5}$$ $$V_n \equiv V_1 = P (mod\ \ n)\tag{5-6}$$

利用上面的结果的素性测试,称为 Lucas 序列素性测试。如果合数通过测试 $(5-1)$,称为以 $P,Q$ 为参数的 lucas 伪素数,简称 lpsp(P,Q)。如果合数通过测试 $(5-2)$,称为以 $P,Q$ 为参数的 lucas-v 伪素数,简称 vpsp(P,Q)。

对 Lucas 序列有如下快速迭代公式。
$$U_{2k} = U_kV_k\tag{5-7}$$ $$V_{2k} = V_k^2 - 2Q^k\tag{5-8}$$ $$U_{k+1} = (PU_k + V_k) / 2\tag{5-9}$$ $$V_{k+1} = (DU_k + PV_k) / 2\tag{5-10}$$

#### A、参数的选择

方法一、$D$ 在序列 $5, -7, 9, -11, 13, -15,\dots$ 中选择第一个满足 $J(\frac{D}{n}) = -1$ 的值,令 $P = 1, Q = \frac{1 - D}{4}$

这个方法,不会设置 $Q = 1$,但是常会设置 $Q = -1$,当 $n \equiv \pm 3 (mod\ \ 10)$ 时,此时 $D = 5$。

计算表明, 当 $Q \equiv \pm 1 (mod\ \ n)$ 时要比 $Q \not\equiv \pm 1 (mod\ \ n)$ 有更多合数满足公式 $(5-3)$、$(5-4)$、$(5-5)$、$(5-6)$,因此有下面的改进方法。

方法二、按照方法一的选择参数,当出现 $Q = -1$时候,置 $D,P,Q$ 都为5。

用方法二的参数,前 10 个 lpsp 是 323,377,1159,1829,3827,5459,5777,9071,9179,10877,$10^{15}$ 以内有 2402549 个 lpsp,vpsp 更稀少,$10^{15}$ 以内只有 5 个 vpsp。
#### B、强 lucas 素性测试

如果 $n$ 是奇素数,$J(\frac{D}{n}) = -1$,$n + 1 = q * 2^s$,$q$ 是奇数,则必有 $r$ 满足 $0 \leq r < s$ 满足下面两个条件之一: $$U_q \equiv 0 (mod\ \ n) \tag{5-11}$$ $$V_{q*2^r} \equiv 0 (mod\ \ n) \tag{5-12}$$

如果 $n$ 是合数,用方法二选择参数$D、P、Q$,$J(\frac{D}{n}) = -1$,满足 $(5-11)$ 或者 $(5-12)$,$n$ 称为强 lucas 伪素数,记做 slpsp(P,Q)。前 10 个 slpsp 是5459,5777,10877,16109,18971,22499,24569,25199,40309,58519。强 lucas 伪素数远少于 lucas 伪素数,$10^{15}$ 以内只有 474971 个。

#### C、BPSW 算法

该算法是对 $n$ 首先进行基 2 的 Miller-Rabin 测试,然后用方法二选择参数进行强 Lucas 素性测试。即:
1、如果 $n$ 没有通过基 2 Miller-Rabin 测试,输出 $n$ 是合数,结束。

2、用方法二选择参数 $D,P,Q$。

3、进行强 lucas 素性测试,通过则输出 $n$ 可能是素数,否则 $n$ 是合数。
#### D、增强的 BPSW 算法

基于 vpsp 很稀少的事实,针对 BPSW 增加了两个检验。

1、如果 $n$ 没有通过基 2 Miller-Rabin 测试,输出 $n$ 是合数,结束。

2、用方法二选择参数 $D,P,Q$。

3、进行强 lucas 素性测试,通过则转步骤 4 进一步检验,否则输出 $n$ 是合数,结束。

4、基于步骤 3 的计算,进一步计算并检验 $5-2$,不满足 $5-2$,则输出 $n$ 是合数,结束。

5、验证 $n$ 是不是满足 $Q^{(n+1)/2} \equiv Q*J(\frac{Q}{n}) (mod\ \ n)$,如果满足,输出 $n$ 可能素数,否则输出 $n$ 是合数。
#### E、实现算法:

输入待测试正奇数 n

1、d = 5, deta = 2

2、测试 $J(\frac{d}{n})$,如果不等于-1,则 deta = -deta, d = deta - d,重复 2。

3、置 D = d, P = 1, Q = (1 - D) / 4,如果 Q = -1,则 D = 5,P = 5,Q = 5。

4、令 $n + 1 = q * 2^s$,$q$ 是奇数,令 $qs$ 表示 $q$ 的二进制表示的长度,即 $2^{qs-1} \le q < 2^{qs}$。$U_c = U_1 = 1, V_c = V_1 = P, Q_c = Q$。

5、若$qs$ > 1,令 $i$ 从 $qs - 2$ 到 $0$ 循环执行 5.1-5.2($qs$ 至少为1,且最高位肯定是1,所以这里从第二个二进制位开始)

5.1 $U_c = U_c * V_c (mod\ \ n),V_c = V_c^2 - 2Q_c (mod\ \ n),Q_c = Q_c^2 (mod\ \ n)$

5.2 如果 $q$ 二进制表示第 $i$ 位是 $1$,则 $U_c = (PU_c + V_c)/2 (mod\ \ n),V_c = (DU_c + PV_c)/2 (mod\ \ n),Q_c = Q_c Q (mod\ \ n) $。

6、此时 $U_c$ 即为 $U_q$,若 $U_c \not = {0}$,执行7,否则跳到9。

7、继续测试 $V_c$。令 $r = 0$,循环执行:

7.1、如果 $V_c = 0$,跳转到9。

7.2、$V_c = V_c^2 - 2Q_c (mod\ \ n),Q_c = Q_c^2 (mod\ \ n), r = r + 1$。如果 $r = s$,跳转到8,否则跳转到 7.1 继续循环。

8、输出 $n$ 是合数,结束。

9、此时,强 lucas 素性测试输出 $n$ 可能是素数,如果进一步测试,进行步骤 10。

10、强化的 BPSW 算法,利用了 5-7 的步骤的计算,附加计算并不多。分成两个检验:

10.1、循环执行 $V_c = V_c^2 - 2Q_c (mod\ \ n),Q_c = Q_c^2 (mod\ \ n), r = r + 1$,直到 $r = s$。

10.2、此时,$V_c = V_{n+1}$,测试 $V_c \equiv 2Q (mod\ \ n)$ 是否成立,如果不成立,输出 $n$ 是合数,结束。

10.3、测试 $Q^{(n+1)/2} \equiv Q*J(\frac{Q}{n}) (mod\ \ n)$ 是否成立,如果不成立,输出 $n$ 是合数,结束。否则,输出 $n$ 通过强化的 BPSW 素性测试,可能是素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-5-22 00:17 , Processed in 0.059527 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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