我是一名计算机科学专业的学生,我正在独立学习算法课程。
在课程中,我看到了这个问题:
显示一个有效的随机算法来计算 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)
如果 Miller-Rabin 在 Carmichael 数 n 上失败,则作为副产品,您会得到一些 x
证明:x
另一方面,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)
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(74条)