Tài liệu Kỹ thuật lập trình - Chương 4: Phân tích số nguyên thành nhân tử

Chia sẻ: | Ngày: | Loại File: DOC | Số trang:14

Thêm vào BST

Báo xấu

152
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phân tích nhân tử là một thuật ngữ toán học dùng để chỉ một cách viết một số nguyên, hay tổng quát là một vật thể toán học, thành một phép nhân của các số nguyên khác, hay tổng quát là các vật thể toán học khác. Các số nguyên, hay vật thể toán học, nằm trong phép nhân gọi là nhân tử. Cùng tham khảo tài liệu dưới đây để tìm hiểu kiến thức về phân tích số nguyên thành nhân tử.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tài liệu Kỹ thuật lập trình - Chương 4: Phân tích số nguyên thành nhân tử

Chương 4 PHÂN TÍCH SỐ NGUYÊN THÀNH NHÂN TỬ 4.1 Nhân tử hóa với độ phức tạp là hàm mũ 4.1.1 Mở đầu Trong mục này chúng ta xem xét các thuật toán phân tích số tự nhiên n ra thừa số, mà nó thực hiện O (n c ) lệnh số học, c là hằng số, 0
[ ] Giá trị ban đầu ( x0 , y0 ) = ( n ,0) . Sự tăng số k diễn ra theo quy tắc sau. Nếu như rk = 0 , thì mục đích của chúng ta đạt được n = xk − y k = ( xk − y k )( xk + y k ) , và thuật toán 2 2 dừng. Nếu như rk > 0 , thì ( xk +1 , y k +1 ) := ( xk , y k + 1) , Nếu như rk < 0 , thì ( xk +1 , y k +1 ) := ( xk + 1, y k ) ; sau đó rk +1 := xk +1 − yk +1 − n 2 2 Chúng ta có thể chứng minh rằng với số bước thực hiện có hạn thì thuật toán đ ưa đến giá trị rk = 0 . 4.1.3 Phương pháp (p-1) Pollaid Thuật toán p-1 của Pollaid đưa ra năm 1974 là một thuật toán đơn giản áp dụng đối với các số nguyên lớn. Thuật toán này dựa vào hai đối số: Số nguyên lẻ n cần phân tích và cận B. Thuật toán được miêu tả như sau: Đầu vào: n và B. Đầu ra: Các thừa số của n (nếu tìm thấy). Bước 1. Cho a=2 Bước 2. For j=2 to B do a = a j (mod n) Bước 3. Tính d=UCLN(a-1,n) Bước 4. Nếu 1 < d < n thì d là một thừa số của n Ngược lại Không tìm thấy thừa số của n. Chúng ta xem tính hợp lý của thuật toán. Giả sử p là một ước số nguyên tố của n. Giới hạn B >0 thỏa mãn điều kiện sau. Với mọi số nguyên tố q | ( p − 1) thì ta có điều kiện: v q ( p −1) q ≤B. Từ đây dẫn đến (p-1)|B! Nếu như chúng ta chọn số tự nhiên n sao cho UCLN(a,n)=1 thì theo định lý nhỏ Fermat:
a B! ≡ 1(mod p ) , Mà (p-1)|B!, nên a ≡ 1(mod p ) , nghĩa là p | (a − 1) , mà ta lại có p|n, cho nên p=UCLN(a-1, n). Trong thuật toán có (B-1) lũy thừa theo modulo, mỗi lũy thừa cần nhiều nhất là 2log2B phép nhân modulo, ở đây chúng ta có thể áp dụng thuật toán bình phương và nhân để thực hiện hiểu quả phép lũy thừa. Việc tính ước chung lớn nhất có thể thực hiện trong thời gian O((log n) 3) bằng thuật toán Euclide. Vì thế độ phức tạp của thuật toán là O(B log B(log n)2+(log n)3). Nếu như B là O((log n)i) với i là một số nguyên nào đó thì độ phức tạp của thuật toán là độ phức tạp thời gian đa thức. 4.1.4 Phương pháp ρ Pollaid Phương pháp này được đề cập khá nhiều trong các sách và báo, nên ở đây chúng ta chỉ nói khá tóm tắt miêu tả thuật toán. Sơ đồ thuật toán Đầu vào: là số nguyên n, mà chúng ta cần phân tích nó ra thừa số. Bước 1. Chọn ánh xạ f : Zn → Zn . Thông thường f (x) là đa thức có bậc không lớn hơn hay bằng 2, ví dụ f ( x) = x 2 + 1 . Bước 2. Chọn ngẫu nhiên x0 ∈ Z n và tính phần tử theo đệ quy của dãy x0 , x1 , x 2 ,... theo quy tắc xi ≡ f ( xi −1 )(mod n) . Bước 3. Đối với một số j, k kiểm tra điều kiện 1 < UCLN ( x j − xk , n) < n Cho đến khi nào không tìm được ước của số n hoặc thời gian chưa kết thúc. Kết thúc thuật toán Chú ý: Sự lựa chọn j, k trong bước 3 của thuật toán thông thường thực hiện một trong các cách sau 1. Đối với từng j chọn tất cả các số k, k
h +1 3. Nếu như j trong giới hạn 2 ≤ j < 2 , h ∈ N , thì cho k = 2 h − 1 h Đây là phương pháp khá đơn giản. Nếu như chu kỳ của dãy xi (mod n) có thể bậc là n, thì chu kỳ của dãy xi (mod p ) đối với ước nguyên tố p của số n không vượt quá p. Điều này có nghĩa là x j , xk có thể khác nhau theo modulo n, nhưng trùng nhau theo modulo p, có nghĩa là p | UCLN ( x j − xk , n) . Phương pháp này cần O(n1 / 4 ) lệnh số học. Nó rất thông dụng và thường được sử dụng để tách ước nguyên tố không lớn của số n. 4.1.5 Phương pháp Serman-Leman Thuật toán này cần O(n1 / 3 ) lệnh số học Thuật toán Đầu vào: Cho n là số lẻ, n>8. Đầu ra: Là các thừa số của n. Bước 1. Đối với a = 2,3,..., [ n1 / 3 ] kiểm tra điều kiện a | n . Nếu như trên bước này chúng ta không phân tích được n ra thừa số, thì chuyển đến bước 2. Bước 2. Nếu như trong bước 1 ước không tìm thấy và n là hợp số, thì n=pq, ở đây p,q là số nguyên tố và n1 / 3 < p ≤ q < n 2 / 3 [ ] Như thế đối với tất cả k = 1,2,..., [ n1 / 3 ] và tất cả d = 0,1,..., n1 / 6 /(4 k ) + 1 , kiểm tra số [ ] ( 4kn + d ) 2 − 4kn có phải là số chính phương hay là không. Nếu là chính phương thì A= [ ] 4kn + d và B = A2 − 4kn thỏa mãn đồng dư thức A2 ≡ B 2 (mod n) . Trong trường hợp này kiểm tra điều kiện 1 < UCLN ( A ± B, n) < n Nếu điều kiện này thỏa mãn thì chúng ta đã phân tích n ra 2 thừa s ố và thuật toán dừng. Kết thúc thuật toán. Nếu thuật toán không phân tích n ra 2 thừa số thì n là số nguyên tố. 4.1.6 Thuật toán Pollaid –Xtrassen Thuật toán này phân tích n thành 2 thừa số cần O(n1 / 4 log 4 n) lệnh số học. Thuật toán cơ bản dựa trên định lý sau
Định lý 4.1 Cho z ∈ N , y = z 2 . Khi đó đối với bất kỳ số tự nhiên t, ước số nhỏ nhất của số UCLN (t , y!) có thể tìm thấy cần O( z log 2 z log 2 t ) lệnh số học. Thuật toán Pollard-Xtrassen Đặt z = [ n1 / 4 ] + 1, y = z 2 > n1 / 2 , t = n . Tiếp theo với sự giúp đỡ của định lý 2.20 chúng ta tìm ước nguyên tố nhỏ nhất của UCLN (n, y!) . Bởi vì y! chia hết cho ước nguyên tố nhỏ nhất p của n (bởi vì p ≤ n1 / 2 < y ), nên thuật toán đưa ra chính là số p. Độ phức tạp của thuật toán Pollard-Xtrassen là O( z log 2 z log 2 t ) = O(n1 / 4 log 4 n) . 4.1.7 Phương pháp nhân tử hóa dành cho các số có dạng đặc trưng Đối với số n có dạng đặc trưng thì có khả năng có các cách riêng đ ể phân tích ra thừa số nguyên tử, bởi vì ước của các số đó có thể có dạng đặc trưng. Định lý 4.2 Cho b, k ∈ N , b > 1, n = b k − 1 . Nếu p là số nguyên tố, và ước của n, thì một trong hai điều khẳng định sau là đúng: 1. p | b d − 1 với một số giá trị của d, d < k , d | k ; 2. p ≡ 1(mod k ) . Nếu như p>2 và k là số lẻ, thì trường hợp thứ hai p ≡ 1(mod 2k ) . Chứng minh: Theo định lý nhỏ Fermat thì b p −1 ≡ 1(mod p ) , cũng như b k ≡ 1(mod p) . Giả sử d = UCLN (k , p − 1) , khi đó b d ≡ 1(mod p ) . Nếu như d < k , thì có nghĩa là điều khẳng định thứ nhất đúng. Còn nếu như d=k, thì k|p-1, có nghĩa là p ≡ 1(mod k ) . 4.2 Phân tích số nguyên thành nhân tử với độ phức tạp là hàm mũ giả 4.2.1 Mở đầu Ký hiệu Ln [γ ; c] là hàm có đặc điểm sau: Lx [ γ ; c ] = e( c + o (1))(log x ) γ (log log x )1−γ , o(1) → 0 , khi x → + ∞, c, γ là hằng số. Trong chương này chúng ta xem các thuật toán nhân tử hóa số tự nhiên n, cần Ln [ γ ; c] 1 1 lệnh số học khi γ = hoặc γ = và một số giá trị dương c, gía trị này phụ thuộc vào 2 3 thuật toán. Chúng ta giả sử rằng, n là hợp số và n không chia hết cho các số nguyên tố nhỏ (những số nguyên tố nhỏ chúng ta tìm bằng cách lựa chọn, hoặc với sự giúp đở của các thuật toán mà chúng ta tìm hiểu trong chương trước).
Thuật toán được miêu tả như sau, cách tìm các số tự nhiên x,y, sao cho x 2 ≡ y 2 (mod n) , sau đó kiểm tra điều kiện 1 < UCLN ( x ± y , n) < n . Nếu như ước của n được tìm , thì thuật toán dừng, ngược lại ta đi xây dựng cặp x,y tiếp theo. Định lý 4.3 Cho n là hợp số lẻ, và giá trị của nó không bằng giá trị của hàm mũ của một số nguyên tố. Khi đó đối với cặp ngẫu nhiên x, y,1 ≤ x, y ≤ n − 1 , thỏa mãn các biểu thức UCLN ( x, n) = UCLN ( y , n) = 1 x 2 ≡ y 2 (mod n) Xác suất để 1 < UCLN ( x ± y , n) < n Sẽ không nhỏ hơn 1/2. α α Chứng minh. Giả sử n = p1 ... pk , k ≥ 2 . Cặp số x,y thỏa mãn điều kiện của định lý, 1 k tương ứng với số z, 1 ≤ z ≤ n − 1, z 2 ≡ 1(mod n) (rõ ràng z = xy −1 (mod n)) . Chúng ta cần chứng minh rằng xác suất để z thỏa mãn bất đẳng thức phụ 1 < UCLN ( z ± 1, n) < n Không nhỏ hơn 1/2. Rõ ràng rằng điều kiện z 2 ≡ 1(mod n) tương đương với hệ phương trình sau α z ≡ ±1(mod p1 1 ), .......................... α z ≡ ±1(mod pk k ) Từ đây, số lượng các giá trị có thể của z bằng 2 k , và chỉ đối với 2 giá trị z ≡ ±1(mod n) thì ước chung lớn nhất UCLN ( z ± 1, n) bằng 1 hay n. Bởi vì k ≥ 2 , nên định lý của chúng ta rõ ràng đúng. 4.2.2 Phương pháp Dixon Cho n∈ N - là số mà chúng ta cần phân tích thành nhân tử, L = L(n) = exp((log n log log n)1 / 2 ) . Giả sử a là hằng số nào đó, 0 < a < 1 , giá trị của nó xác định ở dưới. Chúng ta gọi tập các số nguyên tố p, nằm trong khoảng dưới là cơ sở nhân tử 2 ≤ p ≤ La .
Giả sử k là số lượng các số nguyên tố trong cơ sở nguyên tử, 2 = p1 < p 2 < ... < pk ≤ L . a Thuật toán Dixon. Đâu vào: là số nguyên n cần kiểm tra Bước 1. Chúng ta tìm các số m1 ,..., mk +1 bằng cách lựa chọn ngẫu nhiên, sao cho thỏa mãn 1 < mi < n α α Q(mi ) = p1 i ,1 ... pk i ,k mi2 ≡ Q(mi )(mod n) Và các giá trị pi được dùng là chẳn lần, và với i = 1,..., k + 1 . Ký hiệu v = (α i ,1 ,..., α i , k ∈ Z k . Bước 2. Giải hệ phương trình tuyến tính x1 v1 + ... + xk +1 v k +1 ≡ 0(mod 2) Trong không gian vector Z 2 k , chúng ta tìm được tập x1 ,..., xk +1 ∈ { 0,1} , tập này không bao gồm các giá trị 0 (cái này tồn tại bởi vì số lượng phương trình k nhỏ hơn số ẩn). Bước 3. Để tìm được x1 ,..., xk +1 , rõ ràng ta có biểu thức sau k +1 k +1 ∑ x i α i ,1 ∑ xi α i ,k (m1x1 ...mkx++11 ) 2 ≡ p1i=1 k ... pki=1 (mod n) k +1 k ( ∑ x iα i , j ) / 2  k +1  Ký hiệu X = m ...m ,Y = ∏ p j , (số  ∑ xiα i , j  / 2 -là số nguyên xác định x1 x k +1 i =1 1 k +1 j =1  i =1  theo xi ), chúng ta nhận được biểu thức tương ứng X 2 ≡ Y 2 (mod n) . Tiếp theo chúng ta kiểm tra điều kiện 1 < UCLN ( X ± Y , n) < n Trong trường hợp thành công chúng ta đã phân tích n ra thừa số. Trong trường hợp không thành công thì chúng ta quay lại bước 1 và tìm các giá trị khác của mi Kết thúc thuật toán Ví dụ. Giả sử n=15770708441. Cơ sở nhân tử là tập { 2,3,5,7,11,13} . Chọn m1 = 8340934156 , m2 = 12044942944 , m3 = 2773700011 . Xét ba đồng dư thức sau 83409341562 ≡ 3.7(mod n) 120449429442 ≡ 2.7.13(mod n)
27737000112 ≡ 2.3.13(mod n) Lấy tích 3 đồng dư thức trên vế theo vế, ta được (8340934156.12044942944.2773700011) 2 ≡ (2.3.7.13) 2 (mod n) , rút gọn các biểu thức trong ngoặc theo modulo n, ta có: 95034357852 ≡ 546 2 (mod n) Ta tìm UCLN (9503435785 − 546, n) = 115759 Ta thấy 115759 là một ước của n. 4.2.3 Thuật toán sàng bậc hai Trong thuật toán Dixon, vấn đề là làm thế nào để chọn các số mi mà các giá trị mi2 (mod n) có thể phân tích hoàn toàn trên cơ sở nhân tử. Năm 1981 Pomerance đề xuất phương pháp để xác định các số mi , có tên là sàng bậc hai. 1  Độ phức tạp của thuật toán sàng bậc hai tốn Ln  ;1 lệnh số học. 2  Chúng ta mô tả sơ đồ thuật toán ban đầu sàng bậc hai. Chúng ta xây dựng biểu thức X 2 ≡ Y 2 (mod n) và kiểm tra bất đẳng thức 1 < UCLN ( X ± Y , n) < n Để làm điều này chúng ta xem đa thức Q( x) = ( x + [ n ]) 2 − n ≡ H ( x) 2 (mod n) , ở đây H ( x) = x + [ n ] . Các giá trị Q(x) trong các điểm nguyên, rõ ràng chúng là chính phương theo modulo n. Trong cơ sở nhân tử S chúng ta xem p0 = −1 và tất cả các số n nguyên tố pi , pi ≤ B , sao cho    = 1 . Sau đó với sự giúp đở của một số sàng, chúng ta   pi  tìm giá trị xi , mà Ai = Q( xi ) = ∏ p α ip p∈S , có nghĩa là Q( xi ) phân tích trong cơ sở nhân tử của chúng ta. Như vậy, ký hiệu Bi = H ( xi ) , chúng ta nhận được đồng dư thức Bi2 ≡ Ai (mod n) , chúng ta tích lũy số lượng đủ lớn các biểu thức như thế, chúng ta thực hiện loại bỏ các biến và xay dựng bi ểu thức X 2 ≡ Y 2 (mod n)
n Chú ý: Điều kiện   = 1 với p là số nguyên tố của cơ sở nhân tử lấy từ đồng dư  p   thức ( x + [ n ]) 2 ≡ n(mod p) , mà đồng dư cần thỏa mãn đối với một số giá trị của x ∈ Z . Sàng. Giá trị xi ∈ Z đối với Q( xi ) được xác định như sau. 1. Đối với từng số nguyên tố p từ cơ sở nhân tử, chúng ta tìm nghiệm r1( p ) và r2( p ) của phương trình Q( x) ≡ 0(mod p) . 2. Sau đó chúng ta thay đổi x trong khoảng đủ lớn [ − M ; M ], M ∈ N , chúng ta đưa đến một ma trận A, mà nó được đánh số thứ tự bằng giá trị của x. 3. Trong mỗi phần tử của ma trận với số thứ tự x ta đặt giá trị log Q( x) . Nghĩa là A[ x ] = log | Q( x) | . 4. Sau đó đối với từng giá trị p từ cơ sở nhân tử S chúng ta thực hiện quá trình sàng như sau: Từ mổi phần tử của ma trận A, tức là A[ x] , số thứ tự của nó nằm trong cấp số cộng x ≡ r1( p ) (mod p ) và x ≡ r2( p ) (mod p ) , chúng ta tính toán giá trị của log p . Ý ở đây là việc tính toán nằm ở chổ, đối với phần tử x trong cấp số như vậy, giá trị của Q(x) sẽ chia hết cho p, nhưng việc chia Q(x) cho p chúng ta đổi thành log Q( x) − log p . Sau khi kết thúc quá trình sàng trong phần tử của ma trận với số thứ tự x sẽ chứa giá trị log Q( x ) − ∑ log p . p∈S , p |Q ( x ) Sau khi kết thúc quá trình sàng, chúng ta chọn số thứ tự x, mà ở đó giá tr ị của ma trận cố độ lớn không quá lớn. Đối với các vị trí x như vậy giá trị Q(x) phân tích nhanh hơn trong cơ sở nhân tử của chúng ta và chúng ta phân tích số Q(x) bằng ước số thử và lưu giá trị x, để Ai = Q( xi ) hoàn toàn phân tích trong cơ sở nhân tử của chúng ta. Ý nghĩa của quá trình sàng là tiết kiệm được số lượng lệnh chia các số nguyên l ớn. Cùng với nó là để từng giá trị x ∈ [ − M ; M ] phân tích Q(x) trong cơ sở nhân tử một cách nhanh chóng, chúng ta ước lượt được tập x, và thực hiện tính toán bằng lệnh đơn giản là cộng và trừ. Việc tiết kiệm này là rất hiệu quả, và nó đã được ưu chuộng hơn các thuật toán nhân tử hóa trước đây. 4.2.4 Phân tích ra nhân tử với sự hổ trợ của đường cong Elliptic
Thuật toán phân tích này được Lenstra đề xuất, và độ phức tạp của nó là cần 1/ 2 e (( 2 + o (1)) log p log log p ) log 2 n lệnh số học, p là ước nguyên tố nhỏ nhất của n. Để miêu tả thuật toán Lenstra chúng ta cần đường cong Elliptic không xây dựng trên trường mà là vành Z n , ở đây n là số lẻ, và không chia hết cho 3 hợp số, n là số chúng ta 3 cần phân tích thành nhân tử. Chúng ta xem 3 số ( x, y, z ) ∈ Z n , sao cho iđêal sinh bởi x,y và z trùng với vành Z n . Tập hợp {(ux, uy, uz) | u ∈ Z n * 3 , ( x, y , z ) ∈ Z n ,} 3 gọi là qũy đạo của phần tử ( x, y, z ) ∈ Z n , nó đươc ký hiệu là (x:y:z). Tập tất cả các qũy đạo này ký hiệu P 2 ( Z n ) . Đường cong Elliptic E = Ea ,b trong vành Z n cho bởi phương trình sau y 2 = x 3 + ax + b , * ở đây a, b ∈ Z n ,6(4a 3 + 27b 2 ) ∈ Z n . Chúng ta ký hiệu tập các điểm của đường Elliptic thông qua { } E = Ea ,b ( Z n ) = ( x : y : z ) ∈ P 2 ( Z n ) | y 2 z = x 3 + axz 2 + bz 3 . Tập hợp này là một nhóm Abel hữu hạn, ứng với phép cộng. Thế nhưng chúng ta sẽ sử dụng lệnh nhóm như vậy đối với trường hữu hạn nguyên tố. Chúng ta ký hiệu O = (0 : 1 : 0) ∈ P 2 ( Z n ), Vn = { ( x : y : 1) | x, y ∈ Z n } ∪ { O} Đối với P ∈ Vn và đối với bất kỳ số nguyên tố p, là ước của n, một điểm P từ tập P 2 ( Z p ) ký hiệu là Pp . Rõ ràng rằng Pp = O p khi và chỉ khi P=O. Phép cộng 2 điểm P, Q ∈ Vn được tính như sau. Khi tính P+Q chúng ta hoặc tìm d là ước của n (và mục đích của chúng ta đạt được) hoặc tìm điểm R ∈ Vn mà nó thỏa mãn điều kiện sau. Nếu như p | n, a ≡ a (mod p ) , và nếu như đối với p tìm được b ∈ Z p sao cho, 6(4a + 27b ) ≠ 0 trong Z p và khi đó Pp , Q p ∈ Ea ,b ( Z p ) , thì R p = Pp + Q p trong Ea ,b ( Z p ) . 3 2 Việc tính tổng này được thực hiện như trong cách xây dựng trường hữu hạn bằng đường cong Elliptic.
Chú ý: Nếu như chúng ta có điểm P = ( x : y : 1) , số nguyên tố p và a thì y 2 ≡ x 3 + ax + b(mod n) . Từ đây chúng ta có b ≡ y 2 − x 3 − ax(mod n) . Thế thì xác định được giá trị b ≡ b(mod p ) . Nếu như đối với từng p|n, điểm Q p nằm trên đường cong y 2 ≡ x 3 + ax + b(mod p ) trong trường Z p , thì chúng ta có thể cộng Pp , Q p trên đường cong trong trường Z p và tính tổng P+Q trong trường Z n . Nếu như đối với một số giá trị của p mà điểm Q p không nằm trên đường y 2 ≡ x 3 + ax + b(mod p ) , thì tính tổng P và Q không được thực hiện. Tổng các điểm P và Q từ tập Vn được thực hiện như sau. Nếu như P=O, thì R=Q; Nếu như Q=O thì R=P. Giả sử P, Q ≠ O, P = ( x1 : y1: 1), Q = ( x 2 : y2 : 1) . Chúng ta tìm d = UCLN ( x1 − x2 , n) bằng thuật toán Euclid. Nếu như 1 < d < n , thì chúng ta đã tìm được ước của n, và thuật toán dừng. Nếu như d=1 thì x1 ≠ x2 (mod n) và x1 ≠ x2 (mod p ) đối với số nguyên tố bất kỳ p, p|n. Khi đó chúng ta tìm ( x1 − x2 ) −1 (mod n) bằng thuật toán mở rộng Euclid. Tiếp theo ta đặt λ = ( y1 − y2 )( x1 − x2 ) −1 (mod n) , v = y1 − λx1 (mod n) , x3 = − x1 − x2 + λ2 (mod n) , y3 = −λx3 − v(mod n) . Khi đó theo định nghĩa tổng của P và Q bằng R = P + Q = ( x3 : y3 : 1) . Bây giờ chúng ta xem trường hợp d = UCLN ( x1 − x2 , n) = n . Lúc này x1 ≡ x2 (mod n) . Chúng ta tìm d1 = UCLN ( y1 + y2 , n) . Nếu như 1 < d1 < n thì chúng ta đã tìm được ước của n và thuật toán dừng. Nếu như d1 = n ,nghĩa là y1 ≡ − y2 (mod n) , thì tổng R = P + Q = O . Nếu như d=1, chúng ta tìm λ1 = (3 x12 + a )( y1 + y2 ) −1 (mod n) , v = y1 − λx1 (mod n) , x3 = −2 x1 + λ2 (mod n) , y3 = −λx3 − v(mod n) và giả định R = P + Q = ( x3 : y3 : 1) . Như vậy chúng ta đã xác định được tổng của các điểm của Vn . Bây giờ chúng ta xác định tích của điểm P ∈ Vn với số tự nhiên k. Kết quả phép nhân này hoặc là chúng ta tìm được ước d của n, 1
nhóm Ea ,b ( Z p ) , ở đây thuật toán tìm kPp được nói đến trương chương xây dựng trường hữu hạn bằng đường cong Elliptic. Thuật toán nhân tử hóa với một đường cong Elliptic Đầu vào của thuật toán là số tự nhiên n và các tham số v, w ∈ N ,phụ thuộc vào n. Cũng như a, x, y ∈ Z n , sao cho P = ( x : y : 1) ∈ Vn , đối với b ≡ y 2 − x3 − ax(mod n) thỏa * mãn điều kiện 6(4a 3 + 27b 2 ) ∈ Z n . Thuật toán tìm kiếm ước số tự nhiên d của số n, 1
đường cong. Và lặp lại như thế cho đến khi nào phân tích được n ra thừa s ố hoặc thời gian của chúng ta kết thúc. 4.2.5 Thuật toán sàng trường số học Thuật toán sàng trường số dành phân tích một số nguyên dạng đặc biệt ra thừa số (SNFS). Số n, mà chúng ta áp dụng SNFS có dạng n = r e − s , ở đây r ∈ N , s ∈ Z , r và |s| không quá lớn. Độ phức tạp của thuật toán này là Ln [1 / 3; c ] c là hằng số nào đó. Thực tế sàng trường số không là thuật toán, mà là một phương pháp tính toán, nó bao gồm một số tầng, một trong các tầng nó được phục vụ bằng một số thuật toán. Sơ đồ phương pháp SNFS đối với số n Tầng 1.Lựa chọn cơ sở nhân tử Cơ sở nhân tử bao gồm từ một số tập hợp các phần tử a p ∈ Z n , a p ≠ 0 . Tất cả a p khả nghịch trong vành Z n . Ký hiệu Z P tập hợp vector | P0 | -chiều: 0 { Z P0 = (v p ) p∈P0 | v p ∈ Z } Chúng ta xem ánh xạ * f : Z P0 → Z n (nhóm khả nghịch theo phép nhân các phần tử trong vành Z n ) ∏a vp f ((v p ) p∈P0 ) = p (mod n) . p∈P0 Tầng 2. Tìm mối liên hệ Ở đây chúng ta tìm vector v ∈ Kerf , tức là v = (v p ) p∈P , sao cho 0 ∏a vp p ≡ 1(mod n) p∈P0 Chúng ta cần tìm tập hợp đủ lớn V = { v ∈ Kerf } các vector như thế, chính xác hơn |V| cần phải lớn hơn | P0 | . Tầng 3. Tìm sự phụ thuộc Ở đây chúng ta tìm sự phụ thuộc tuyến tính không tầm thường theo modulo 2 của các vector tìm được v ∈ V ; số lượng của nó lơn hơn so với kích thước của nó, cho nên sự phụ thuộc như vậy là tồn tại. Để tìm sự phụ thuộc chúng ta giải hệ phương trình tuyến tính ∑z v j j j ≡ 0(mod 2)
ở đây V = {v j } . Giải hệ phương trình này chúng ta tìm được tập hợp con không rổng W ⊆ V , mà ∑ v = 0(mod 2) v∈W 1 Lúc này w = ∑ v , với 2w ∈ Kerf . Điều này có nghĩa là khi X ≡ f (W )(mod n) thì 2 v∈W chúng ta có X 2 ≡ f (2W ) ≡ 1(mod n) . Lúc này chúng ta kiểm tra bất đẳng thức sau có đúng hay không 1 < UCLN ( X ± 1, n) < n Nếu như bất đẳng thức đúng thì chúng ta tìm được ước của n, và chúng ta d ừng, ngược lại chúng ta quay về hoặc tầng 2 (tìm liên hệ mới), hoặc tầng 1 (xây dựng một cơ sở nhân tử mới) Kết thúc sơ đồ