prime-factoring - 米勒-拉宾 SPOJ WA

Question

我正在尝试第一次实施 Miller-Rabin。我的代码为所有测试用例给出了正确的答案，我试过但仍然在 SPOJ 上给出了错误的答案。问题陈述：如果输入的数字是素数，我应该打印“YES”，否则“NO”请帮助：

问题链接：http ://www.spoj.com/problems/PON/

代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define LL long long
LL expo(LL a,LL b,LL c)
{
    LL x=1,y=a;
    if(b==0)
            return 1;
    while(b)
    {
            if(b%2==1)
                      x=(x*y)%c;
            y=(y*y)%c;
            b=b/2;
    }
    return x;
}
int main()
{
    LL t,s,x,a,n,prime,temp;
    scanf("%lld",&t);
    srand(time(NULL));
    while(t--)
    {
              scanf("%lld",&n);
              if(n<2)
                     puts("NO");
              else if(n==2)
                      puts("YES");
              else if(n%2==0)
                   puts("NO");
              else
              {
                  s=n-1;
                  prime=1;
                  while(s%2==0)
                               s=s/2;
                  for(int i=0;i<20;i++)
                  {
                          a=rand()%(n-1)+1;
                          x=expo(a,s,n);
                          temp=s;
                          while((temp!=n-1)&&(x!=1)&&(x!=n-1))
                          {
                                                       x=(x*x)%n;
                                                       temp*=2;
                          }
                          if((x!=n-1)&&(temp%2==0))
                          {
                                               prime=0;
                                               break;
                          }
                  }        
                  if(prime==0)
                              puts("NO");
                  else
                      puts("YES");           
              }
    }
    return 0;
    }

Answer 1

我认为您对s和d的计算不正确：

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d % 2 == 0
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1 return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return Composite

我在我的博客上的一篇文章中讨论了 Miller-Rabin 方法。

Answer 2

由于整数溢出，您得到了错误的答案，因为您将 2 个 long 数字相乘，该数字不能保存在单个 long long 类型中。

这是解决问题的python解决方案

import random
_mrpt_num_trials = 25  # number of bases to test

def is_probable_prime(n):
    assert n >= 2
    # special case 2
    if n == 2:
        return True
    # ensure n is odd
    if n % 2 == 0:
        return False
    # write n-1 as 2**s * d
    # repeatedly try to divide n-1 by 2
    s = 0
    d = n - 1
    while True:
        quotient, remainder = divmod(d, 2)
        if remainder == 1:
            break
        s += 1
        d = quotient
    assert(2 ** s * d == n - 1)

    def try_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2 ** i * d, n) == n - 1:
                return False
        return True  

    for _ in range(_mrpt_num_trials):
        a = random.randrange(2, n)
        if try_composite(a):
            return False

    return True  

for i in range(int(input())):
    a = int(input())
    if is_probable_prime(a):
        print("YES")
    else:
        print("NO")

Answer 3

请记住，puts将换行符附加'\n'到您提供的字符串中。你可以试试printf。