生成指定位数强Lucas校验伪素数-Arnault1995构造法

Arnault在1995年的论文《Constructing Carmichael Numbers which are Strong Pseudoprimes to Several Bases》提出了一种用于构造强Lucas校验伪素数的方法，本文将对其方法做具体的实现分析。

1.Lucas素数测试

参考：Albrecht, Martin R., et al. “Prime and prejudice: primality testing under adversarial conditions.” Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018.

1.1 Lucas序列

设$P$和$Q$是整数，且$D=P^2-4Q$，则卢卡斯序列$U_k$和$V_k$如下（$k\ge 0$）:

$$\begin{gathered} U_{k+2}=P{U}_{k+1}-Q{U}_k,U_0=0,U_1=1 \\ {V}_{k+2}=P{V}_{k+1}-Q{V}_k,V_0=2,V_1=P \end{gathered}$$

实际上也可以这么理解，设$\alpha$和$\beta$分别是方程$x^2-Px+Q$的两个根，则有：
U ( P , Q ) = { ( U k ( P , Q ) ) } k ≥ 0 = { α k − β k α − β } k ≥ 0 V ( P , Q ) = { ( V k ( P , Q ) ) } k ≥ 0 = { α k + β k } k ≥ 0 U(P,Q)=\{(U_{k}(P,Q)) \}_{k\ge 0}=\{ \frac{\alpha^{k}-\beta^{k}}{\alpha-\beta}\}_{k\ge 0}\\ V(P,Q)=\{(V_{k}(P,Q)) \}_{k\ge 0}=\{ \alpha^{k}+\beta^{k}\}_{k\ge 0}\\ U(P,Q)={(Uk​(P,Q))}k≥0​={α−βαk−βk​}k≥0​V(P,Q)={(Vk​(P,Q))}k≥0​={αk+βk}k≥0​

1.2 Lucas定理

设$p$是素数，且$gcd(p,2QD)=1$，则有：
$$U_{p-(\frac{x}{p})}\equiv 0(modp)$$

其中$(\frac{x}{p})$表示勒让德符号。

1.3 Lucas素数测试

针对不同的$P$和$Q$，重复测试Lucas定理的逆否。

1.4 Lucas伪素数

如果$n$是一个合数，满足$gcd(n,2QD)=1$，如果$U_{n-(\frac{x}{n})}\equiv 0(modn)$，则$n$是在参数$(P,Q)$下的伪素数。

1.5 Lucas定理2

设$p$是一个素数，且$p\nmid 2QD$，设$p-(\frac{D}{p})=2^{k}q$，$q$为奇数，则以下至少有一个条件满足：

$$p\mid U_q\text{ or }\exists i\text{ such that }0\le i<k\text{ and }p\mid V_{2^{i}q}\text{. }$$

1.6 强Lucas素数测试

针对不同的$P$和$Q$，重复测试Lucas定理2的逆否。

1.7 强Lucas伪素数

如果$n$是一个合数，且$gcd(n,2QD)=1$，设$n-(\frac{D}{n})=2^{k}q$，$q$为奇数，且以下至少有一个条件满足：

$$n\mid U_q\text{ or }\exists i\text{ such that }0\le i<k\text{ and }n\mid V_{2^{i}q}\text{. }$$

2.Arnault1995提出的强伪素数构造方法

参考：Fran ̧cois Arnault. Constructing Carmichael numbers which are strong pseudoprimes to several bases. Journal of Symbolic Computation, 20(2):151–161, 1995.
以下简称Arnault1995。

2.1 大致思路

在做Baillie-PSW测试的时候，一般采用Selfridge’s Method A方法选择参数。
Selfridge’s Method A：
设$D$为$5,-7,9,-11,13,...$的第一个元素，且满足$(\frac{D}{n})=-1$，设$P=1$，$Q=\frac{1-D}{4}$。

构造思路：

假设我们要构造的合数$n$满足$(\frac{5}{n})=-1$，依据Selfridge’s Method A确定的参数应该为$(P,Q,D)=(1,-1,5)$。

1.设合数$n=p_1{p}_2{p}_3$，其中$p_i$均为素数，且$p_i=k_i(p_1+1)-1$，$i\in [2,3]$，$k_2$和$k_3$均为奇数。

2.$p_i$必须满足以下条件（Arnault1995 Lemmas 6.1 and 6.2）：

$$(\frac{D}{p_i})=(\frac{Q}{p_i})=-1,i\in [1,3]$$
在参数$(P,Q,D)=(1,-1,5)$的情况下：
$$(\frac{-1}{p_i})=(\frac{5}{p_i})=-1,i\in [1,3]$$

可以发现$(\frac{-1}{p_i})=-1\iff p_i\equiv 3(mod4)$，$(\frac{5}{p_i})=-1\iff p_i\equiv 2\text{or}3(mod5)$，又对$i\in [2,3]$来说，$p_i=k_i(p_1+1)-1$。由中国剩余定理可以解得：

$$\{\begin{array}{rl}{p}_1& \equiv 3\text{or}7(mod20)\\ p_i& \equiv 2\text{or}3(mod5),i\in [2,3]\end{array}$$

3.添加条件确保$k_2$和$k_3$确实是整数。
$$\{\begin{array}{rl}{p}_1& \equiv k_3^{-1}(mod{k}_2)\\ p_1& \equiv k_2^{-1}(mod{k}_3)\end{array}$$

满足上述三个条件的$n$即为一个强Lucas伪素数。

2.2 生成指定位数的强Lucas伪素数（code this）

假设要生成$t$位的强Lucas伪素数$n$，可以联立三个关于$p_1$的同余方程：
$$\{\begin{array}{rl}{p}_1& \equiv k_3^{-1}(mod{k}_2)\\ p_1& \equiv k_2^{-1}(mod{k}_3)\\ p_1& \equiv 7(mod20)\end{array}$$

通过中国剩余定理，能解出通解$p_1$和特解$x$:

$$\begin{gathered} M=20\ast k_2{k}_3 \\ x=CRT([k_3^{-1}(mod{k}_2),k_2^{-1}(mod{k}_3),7],[k_2,k_3,20]) \\ {p}_1=kM+x,k\in \mathbb{Z} \end{gathered}$$

我们通过调整通解中的系数$k$即可得到指定位数的$p_1$，我们可以通过$t$来计算$p_1$的大致系数$k_{p1}$：

$$\begin{gathered} p_2=k_2(p_1+1)-1=k_2{p}_1+k_2-1 \\ {p}_3=k_3(p_1+1)-1=k_3{p}_1+k_3-1 \\ n=p_1{p}_2{p}_3=k_2{k}_3{p}_1^3+D \\ D=p_1(2k_2{k}_3{p}_1+k_2{k}_3+1-(p_1+1)(k_2+k_3)))\approx 2k_2{k}_3{p}^2\ll k_2{k}_3{p}_1^3 \\ {k}_{p1}\ge (\frac{2^{t-1}}{k_2{k}_3}{)}^{-3}(modM)-1 \end{gathered}$$

在计算出$p_1$后，通过$p_i=k_i(p_1+1)-1$，$i\in [2,3]$计算$p_2$和$p_3$，同时需要保证满足$p_i\equiv 2\text{or}3(mod5),i\in [2,3]$。

代码如下（sage）：

from random import randint

def generate_lucas_pseudoprimes(t):
    assert t >= 64, "Smaller numbers you can debug yourself!"
    while True:
        k2 = randint(1, 200) * 2 + 1
        k3 = randint(1, 200) * 2 + k2
        if k2 % 5 == 0 or k3 % 5 == 0:
            continue
        if gcd(k2, k3) != 1:
            continue
        M = k2 * k3 * 20
        x = crt([7, pow(k3, -1, k2), pow(k2, -1, k3)], [20, k2, k3])
        k = int((2 ** (t - 1) // (k2 * k3)) ** (1 / 3)) // M - 1
        p1 = M * k + x
        p2 = k2 * (p1 + 1) - 1
        p3 = k3 * (p1 + 1) - 1
        if p2 % 5 not in [2, 3] or p3 % 5 not in [2, 3]:
            continue
        # Enumerating k
        while True:
            k += 1
            p1 = M * k + x
            if not is_prime(p1):
                continue
            p2 = k2 * (p1 + 1) - 1
            p3 = k3 * (p1 + 1) - 1
            n = p1 * p2 * p3
            if n.nbits() < t:
                continue
            if n.nbits() > t:
                break
            if not is_prime(p2) or not is_prime(p3):
                continue
            break
        if n.nbits() == t:
            break
    return n, p1, p2, p3
n, _, _, _ = generate_lucas_pseudoprimes(512)
print(n)
from Crypto.Math.Primality import lucas_test
print(lucas_test(int(n)))

ATFWUS 2023-11-21