Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 21 kết quả

Đề tài: Three-way formulas based on field extension

  1. #1
    Ngày gia nhập
    04 2015
    Bài viết
    22

    Mặc định Three-way formulas based on field extension

    em đang viết chương trình nhân 2 phương trình dưới dạng nhị phân,bằng cách chia thành 3 phần theo thuật toán trên (nó nằm ở mục 4 trong bài viết ở đường link dưới ). nhưng nó ra kết quả ko đúng mà em sửa mấy hôm r không được nên lên đây xin hỏi ý kiến các bác.

    đây là kết quả em làm ra và so sánh với kết quả đúng
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		result.png
Lần xem:	7
Size:		7.7 KB
ID:		53529'
    đây là thuật toán
    http://cacr.uwaterloo.ca/techreports...acr2011-30.pdf

    cách làm của em như sau:
    1. tìm chiều dài bit của 2 số (số mũ của 2 phương trình). sau đó tách mỗi phương trình (số) trên thành 3 phần với độ dài (số mũ lớn nhất) bằng độ dài bit lớn nhất chia cho 3 ( = m). em nghỉ phần này có lẻ ko sai vì em đã thử ghép lại và kết quả đúng với số ban đầu.
    2. sau khi có các phần cần thiết thì tiến hành theo các bước tiếp theo của thuật toán
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		1.png
Lần xem:	4
Size:		22.1 KB
ID:		53533
    phần này thì em khá nghi ngờ vì em ko hiểu rõ là tại sao mình phải chuyển đổi giữa 2 trường là GF(2) VÀ GF(4). ở đây em chọn alpha=2 (0010) và alpha+1=3 (0011).
    A0,A1,A2 B0,B1,B2 là các phần đã tách ra của 2 phương trình A và B.
    3. sau đó tìm ra kết quả bằng công thức
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		2.png
Lần xem:	1
Size:		15.3 KB
ID:		53531
    viết lại
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		3.png
Lần xem:	1
Size:		62.5 KB
ID:		53532

    ở đây X^(n/3) em tính bằng cách cho 1 lùi trái m lần (1<<m) và tương tự cho X^(2n/3) và X^n là (1<<2*m) và (1<<3m)

    trình tiếng anh em còn gà nên có thể hiểu sai chổ nào mong các bác giúp em với ạ.
    em cảm ơn.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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

    Dùng cả GF(4) là do thuật toán Toom-Cook phải tính ở 5 chỗ mà F(2) có 0 với 1 thôi nên F(4) là vừa đủ không dư.
    Đã được chỉnh sửa lần cuối bởi prog10 : 02-05-2017 lúc 05:50 PM.

  3. #3
    Ngày gia nhập
    04 2015
    Bài viết
    22

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Câu này khoai thật. Mình cũng chả hiểu cái đa thức to khủng vậy mà dùng field có chút xíu vậy kết quả nó là cái gì

    Còn dùng cả GF(4) là do thuật toán Toom-Cook phải tính ở 5 chỗ mà GF(2) có 0 với 1 thôi nên GF(4) là vừa đủ không dư.
    chổ này thì em hiểu chỉ là thấy hơi lại là sao ko dùng hẳn GF(4) lun mà nó dùng chung cả GF(2) vs GF(4) thôi.
    anh cho em hỏi cách làm của em đúng ko?

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

    Trích dẫn Nguyên bản được gửi bởi shadow596 Xem bài viết
    chổ này thì em hiểu chỉ là thấy hơi lại là sao ko dùng hẳn GF(4) lun mà nó dùng chung cả GF(2) vs GF(4) thôi.
    Do F(4) tính cực hơn F(2) (một số bảng cho thấy rõ luôn) nên hạn chế sử dụng thôi.
    Đã được chỉnh sửa lần cuối bởi prog10 : 02-05-2017 lúc 05:55 PM.

  5. #5
    Ngày gia nhập
    04 2015
    Bài viết
    22

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Do F(4) tính cực hơn F(2) (một số bảng cho thấy rõ luôn) nên hạn chế sử dụng thôi.
    vậy nó khác nhau gì đâu ạ. GF(4) cũng chứa 0 và 1 mà.

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

    Mặc định Three-way formulas based on field extension

    Có khi là do đổi context (F(4) <-> F(2)) nên dễ nhầm và viết sai.

  7. #7
    Ngày gia nhập
    04 2015
    Bài viết
    22

    anh kiểm tra code hộ em cái. sửa mấy hôm r mà chưa đc.

    ở đây
    add_pol là hàm cộng 2 da thức (XOR)
    mul_pol hàm nhân 2 đa thức
    m_setbit(A,m) gán 1 vào vị trí m trong đa thức A

    Code:
    void three_way(M_LONG A, M_LONG B, M_LONG &C)
    {
    	M_LONG P0, P1, P2, P3, P4, tmp,R1,R2,R3, m0, m1, m2, n0, n1, n2;
    	M_LONG alpha;
    	alpha[0] = 1; alpha[1] = 2;
    	unsigned int mA = deg(A), mB = deg(B);
    	unsigned int n = mA < mB ? mB : mA;//lay do dai bit dai nhat
    	int m = (n+2) / 3,h=0;
    	int l = 0;
    	
    	l = m % 32; 
    	h = m/32;
    	
    	split3_pol(A, h, l, m0, m1, m2);chia polynomial thanh 3 phan
    	split3_pol(B, h, l, n0, n1, n2);
    	
    	
    	mul_pol(m0, n0, P0);//P0=m0*n0 nhan 2 polynomil
    	//P1=(m0+m1+m2)*(n0+n1+n2)
    	add_pol(m0, m1, P2);//cong 2 polynomial
    	add_pol(m2, P2, P2);
    
    	add_pol(n0, n1, tmp);
    	add_pol(n2, tmp, tmp);
    	mul_pol(P2, tmp, P1);
    	//P2 = (A0 + A2 + α(A1 + A2))(B0 + B2 + α(B1 + B2))
    	add_pol(m0, m2, P3);
    	add_pol(m1, m2, P4);//A1 + A2
    	mul_pol(P4, alpha, R1);//α(A1 + A2)
    	add_pol(P3, R1, P4);
    	//m_shl(P2, 1);
    	add_pol(n0, n2, P3);
    	add_pol(n1, n2, P2);
    	mul_pol(P2, alpha, R2);//α(B1 + B2)
    	add_pol(P3, R2, tmp);
    
    	mul_pol(tmp, P4, P2);
    	
    	//P3 = (A0 + A1 + α(A1 + A2))(B0 + B1 + α(B1 + B2))
    	add_pol(m0, m1, P3);
    	add_pol(P3, R1, tmp);
    
    	add_pol(n0, n1, R3);
    	add_pol(R2, R3, R3);
    
    	mul_pol(R3, tmp, P3);
    	//P4 = A2B2
    	mul_pol(m2, n2, P4);
    
    	M_LONG Xn, X2n, X3n, U1, U2, U3, U4, U5, U6, U7;
    	int k = h + 1;
    	m_zero(Xn, k); l = k * 2; m_zero(X2n, l); l += k; m_zero(X3n, l);
    	m_setbit(Xn, m); k = 2 * m; m_setbit(X2n, k); k += m; m_setbit(X3n, k);
    	while (Xn[Xn[0]] == 0)
    		Xn[0]--;
    	while (X2n[X2n[0]] == 0)
    		X2n[0]--;
    	while (X3n[X3n[0]] == 0)
    		X3n[0]--;
    	
    
    	add_pol(P2, P3,U1);//U1=P2+P3
    	mul_pol(alpha, U1, U2);//U2 = αU1 (= α(P2 + P3)) 
    	//m_copy(U2, U1); m_shl(U2, 1);
    	//mul_pol(three, U1, U3);
    //U3 = (1 + α)U1 (= (1 + α)(P2 + P3))
    	add_pol(U1, U2, U3);
    	add_pol(P1, U3, U4);//U4 = P1 + U3 (= P1 + (1 + α)(P2 + P3))
    	//U5 = U4(Xn/3 + X2n/3 + X3n/3)
    	add_pol(Xn, X3n, tmp);
    	add_pol(X2n, tmp, tmp);
    	mul_pol(tmp, U4, U5);
    	
    	//U6 = P0 + Xn/3P4 (= P0 + Xn/3P4)
    	mul_pol(Xn, P4, U6);
    	add_pol(P0, U6, U6);
    	
    	//U7 = U6(1 + Xn) (= P0 + Xn/3P4)(1 + Xn))
    	mul_pol(U6, X3n, U7);
    	add_pol(U6, U7, U7);
    	
    	//C = U7 + U5 + XnU2 + P2X2n/3 + P3Xn/3
    	add_pol(U7, U5, tmp);
    	mul_pol(X3n, U2, R1);
    	mul_pol(P2, X2n, R2);
    	mul_pol(P3, Xn, R3);
    	//m_shl(R3, 4);
    	add_pol(tmp, R1, C);
    	add_pol(R2, C, C);
    	add_pol(R3, C, C);
    	
    	while (C[C[0]] == 0)
    		C[0]--;
    }

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

    Mình nghĩ là không thể dùng lại phép nhân của F(2) được.

    Ví dụ: Xem x+1 là đa thức bậc 0 với F(4) thì (x+1)(x+1) = x^2+2x+1 = x+1+1 = x (F(4)) nhưng với F(2) thì kết quả là x^2+1.
    Đã được chỉnh sửa lần cuối bởi prog10 : 07-05-2017 lúc 03:03 PM.

  9. #9
    Ngày gia nhập
    04 2015
    Bài viết
    22

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Mình nghĩ là không thể dùng lại phép nhân của F(2) được.

    Ví dụ: Xem x+1 là đa thức bậc 0 với F(4) thì (x+1)(x+1) = x^2+2x+1 = x+1+1 = x (F(4)) nhưng với F(2) thì kết quả là x^2+1.
    ý anh là chỗ này Click vào hình ảnh để lấy hình ảnh lớn

Tên:		1.png
Lần xem:	2
Size:		11.7 KB
ID:		53809 phải tích theo phép nhân của F(4) ấy ạ

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

    Trích dẫn Nguyên bản được gửi bởi shadow596 Xem bài viết
    ý anh là chỗ này Click vào hình ảnh để lấy hình ảnh lớn

Tên:		1.png
Lần xem:	2
Size:		11.7 KB
ID:		53809 phải tích theo phép nhân của F(4) ấy ạ
    Đúng vậy bạn .
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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