Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Độ chuẩn xác của thuật toán Rabin-Miller

  1. #1
    Ngày gia nhập
    07 2011
    Bài viết
    11

    Mặc định Độ chuẩn xác của thuật toán Rabin-Miller

    Mình có cài đặt thuật toán Rabin-Miller theo cả hướng dẫn của Wikipedia tiếng Việt lẫn tiếng Anh, do một số test thử sai nên mình đã mượn code Rabin-Miller từ một số nguồn khác (VNOI ...) nhưng khi thử các test trên vẫn sai, mặc dù đã để t lên đến 50.
    Các bạn cho mình hỏi là thuật toán mình cài sai hay như thế nào mà lại không chính xác thế nhỉ.

    Code:
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    bool isprime(unsigned long n)
    {
         if(n==1) return false;
         for (unsigned long i=2;i*i<=n;i++)
             if(n%i==0) return false;
         return true;
    }
    unsigned long power(unsigned long base,unsigned long exponent,unsigned long modulus)
    {
         unsigned long result=1;
         while (exponent>0)
         {
               if (exponent%2==1)
                  result=(result*base)%modulus;
               exponent/=2;
               base=(base*base)%modulus;
         }    
         return result;
    }
    bool miller_rabin(unsigned long n,int t)
    {
    	 srand(unsigned (NULL));
         if (n<=50) return isprime(n);
         unsigned long m=n-1;
         int r,k=0;
         if (n%2==0)return false;
         while (m%2==0)
         {
               m=m/2;
               k++;
         }
         for (int i=0;i<t;i++)
         {
             r=k;
             unsigned long a=rand()%(n-2)+2;
             unsigned long b=power(a,m,n);
             if (b!=1&&b!=n-1)
             {
                while (r>=0)
                {
                      b=power(b,2,n);
                      if(b==n-1)break;
                      r--;
                }
                if (r<0)return false;
             }    
         }
         return true;
    }
    
    
    int main()
    {
    	cout << isprime(1234577) << endl;
    	cout << miller_rabin(1234577,50) << endl;
    	//system("pause");
    	return 0;
    }

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Cái code trên là của mình
    Bạn sửa lại ở chỗ long long thành long.
    Kết quả sai vì... phép nhân trong hàm power sẽ làm tràn số...

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    11

    Thanks bạn nha, à cho mình hỏi thêm cái này với: khi mình đọc mã giả của wiki tiếng anh với tiếng việt thì có một số khác nhau, không biết có ảnh hưởng đến thuật toán không ?

    write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
    LOOP: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then do next LOOP
    for r = 1 .. s − 1
    x ← x2 mod n
    if x = 1 then return composite
    if x = n − 1 then do next LOOP
    return composite
    return probably prime
    1. Phân tích n-1 = 2^s nhân m trong do s >= 1 và m là số tự nhiên lẻ
    2. Chọn ngẫu nhiên số tự nhiên a thuộc {2,...,n-1}.
    3. Đặt b = am(mod n)
    4. Nếu b == 1 thì trả về TRUE. Kết thúc.
    5. Cho k chạy từ 0 đến s-1:
    1. Nếu b == -1 thì trả về TRUE. Kết thúc.
    2. Thay b:=b2(mod n).
    6. Trả lời FALSE. Kết thúc.
    Tiện thể cho mình hỏi lun, với những số có giá trị dưới 2 tỷ thì nên đặt t bằng mấy để có độ chính xác cao nhất và tiết kiệm thời gian và chi phí nhất? (Có một số bảo nên đặt 4 - 5)

  4. #4
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Lúc mình code bài này đọc bản dịch tiếng Việt , mình nghĩ là không có vấn đề gì
    Bạn xem bài PAGAIN ở spoj, mình để k=5 submit AC, rejugle lại thì WA :(
    Mình nghĩ để 10 là ổn ^^

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  5. #5
    Ngày gia nhập
    07 2011
    Bài viết
    11

    mình để 6 cũng được AC

  6. #6
    Ngày gia nhập
    01 2013
    Bài viết
    1,477

    Mặc định Độ chuẩn xác của thuật toán Rabin-Miller

    Số < 4b thì 2 7 61 là 100% đúng (do test ta có)
    Paper về chọn random base cho R-M: http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1189518-9/
    Chỉ cần làm sao mà xác suất pseudoprime < 1e-40 hay 1e-60 là đc.

    R-M cũng tốt thật nhưng có test mạnh hơn R-M (chưa tìm thấy pseudoprime nào) và cũng phức tạp hơn.
    Đã được chỉnh sửa lần cuối bởi prog10 : 02-04-2015 lúc 12:13 AM.

Các đề tài tương tự

  1. Bài tập C Thuật toán cho chương trình C chuẩn hóa một đoạn văn?
    Gửi bởi tam826 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 24-03-2013, 01:32 AM
  2. Dịch thuật với các quy chuẩn 8 bước cho chất lượng dịch tốt nhất
    Gửi bởi quocquang356 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 28-11-2012, 07:02 AM
  3. Nhận dịch thuật tiếng hàn quốc giá rẻ dịch chuẩn
    Gửi bởi thachdinh908 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 21-10-2012, 11:07 PM
  4. công ty dịch thuật dịch cực chuẩn anh chị em ủng hộ
    Gửi bởi hoanghanh99 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 27-07-2012, 07:08 AM
  5. Kiểm tra số nguyên tố theo thuật toán miller-rabin. Giúp mình sửa lỗi
    Gửi bởi tranduchoan trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 7
    Bài viết cuối: 01-03-2011, 06:49 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn