果味c宾:拉宾-米勒对Carmichael数的检验

关于果味c宾的问题,在miller rabin algorithm中经常遇到, 我是一名计算机科学专业的学生,我正在独立学习算法课程。

我是一名计算机科学专业的学生,我正在独立学习算法课程。

在课程中,我看到了这个问题:

显示一个有效的随机算法来计算 Carmichael 数(也就是说,我们想要一个多项式时间算法,给定任何 Carmichael 数 C,至少有 3 / 4 的概率找到 C 的非平凡因子)。提示:使用 Rabin-Miller 检验。

我的解决方案:

我的想法是使用 Rabin-Miller 测试:我将检查 C 是否是素数我将使用 Rabin-Miller 素数测试步骤:

求 n-1 = c ^ k * m

选择 a:1 & lt;a & lt;n-1

计算 b_0 = a ^ m (mod n),b_i = b_(i-1) ^ 2 (mod n)

如果 b_0 =-/ + 1,这是素数,我将不返回任何东西。如果 b_i =-1,这是素数,将不返回任何东西。否则,如果 = 1,这不是素数,我将返回 C 的因子。

算法:

function MillerRabinPrimality(n)
    Input: integer n, Carmichael number
    Output: return with probability 3/4 nontrivial factor of n
    Find integers k,q > 0, q odd, so that (n-1)=2^(k)
    Select a random integer a, 1<a<n-1
    if a^q mod n = +/-1 
        return 'this prime'
    for j = 0 to k-1 do
        a = a^2 mod q
        if (a = -1)
            return 'this prime'
        if (a = 1)
            return 'this is composite, factor is ?'     

我不知道如何返回 c 的因子,例如我为 561 运行 Rabin-Miller 素数测试,第一个 carmichael 数:

n = 561
n-1 = 2(^k)*m => 560
560/2^1 = 280 => 560/2^2 = 140 => 560/2^3 = 70 => **560/2^4 = 35** 
k = 4
m = 35
choose a: 1<a<560
a = 2
b_0 = 2^35 mod 561 = 263
b_1 = 263^2 mod 561 = 166
b_2 = 166^2 mod 561 = 67
b_3 = 17^2 mod 561 = 1 --> composite 
i found that 561 is composite but not sure how to return his factors (3 / 11 / 17)
3

如果 Miller-Rabin 在 Carmichael 数 n 上失败,则作为副产品,您会得到一些 x± 1 mod n,使得 x ² ≡ 1 mod n。gcd(x 1,n)和 gcd(x − 1,n)都是 n 的适当除数。

证明:x1 mod n 等效于 x −10 mod n,这等效于 x − 1 不能被 n 整除。因此 gcd(x − 1,n)≠ n。同样,x-1 mod n 表示 gcd(x 1,n)≠ n。

另一方面,x ² ≡ 1 mod n 等于(x 1)(x-1)可被 n 整除,因此 gcd((x 1)(x-1),n)= n。我们不能有 gcd(x 1,n)= 1,否则 gcd(x-1,n)= n(因为 gcd(a b,c)= gcd-1(a,cd)

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(333)
Plc编程中最常用的编程语言:以编程方式访问Windows8.1中最常用的应用程序
上一篇
Cma和中级会计师哪个含金量高:好理发师 com-他们使用的是哪个控件
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(74条)