ecm - Trực tuyến trên đám mây

CHƯƠNG TRÌNH:

TÊN

ecm - thừa số nguyên bằng ECM, P-1 hoặc P + 1

SYNOPSIS

ecm [lựa chọn] B1 [B2 phút-B2max | B2]

MÔ TẢ

ecm là một chương trình tính toán số nguyên sử dụng Phương pháp Đường cong Elliptic (ECM), phương pháp P-1,
hoặc phương pháp P + 1. Các phần sau đây mô tả các thông số liên quan đến những
các thuật toán.

STEP 1 VÀ STEP 2 giới hạn THÔNG SỐ

B1
B1 là bước 1 bị ràng buộc. Nó là một tham số bắt buộc. Nó có thể được cho dưới dạng số nguyên
định dạng (ví dụ: 3000000) hoặc ở định dạng dấu phẩy động (3000000.0 hoặc 3e6). Các
lớn nhất có thể B1 giá trị là 9007199254740996 cho P-1 và ULONG_MAX hoặc
9007199254740996 (tùy theo giá trị nào nhỏ hơn) cho ECM và P + 1. Tất cả các số nguyên tố 2 <= p <= B1 đang
đã xử lý ở bước 1.

B2
B2 là bước 2 bị ràng buộc. Nó là tùy chọn: nếu bỏ qua, một giá trị mặc định được tính từ
B1, nên gần với mức tối ưu. Như B1, nó có thể được cho dưới dạng số nguyên hoặc trong
định dạng dấu phẩy động. Giá trị lớn nhất có thể có của B2 là khoảng 9e23, nhưng
phụ thuộc vào số lượng khối k nếu bạn chỉ định -k Lựa chọn. Tất cả các số nguyên tố B1 <= p <=
B2 được xử lý ở bước 2. Nếu B2 < B1, không có bước 2 nào được thực hiện.

B2 phút-B2max
cách khác, người ta có thể sử dụng B2 phút-B2max hình thức, có nghĩa là tất cả các số nguyên tố B2 phút <= p
<= B2max nên được xử lý. Do đó xác định B2 chỉ tương ứng với B1-B2. Giá trị
of B2 phút và B2max có thể lớn tùy ý, nhưng sự khác biệt của chúng không được vượt quá
khoảng 9e23, tùy thuộc vào số khối k.

Bao thanh toán PHƯƠNG PHÁP

-pm1
Thực hiện P-1 thay vì phương pháp mặc định (ECM).

-pp1
Thực hiện P + 1 thay vì phương pháp mặc định (ECM).

NHÓM VÀ Bước đầu ĐIỂM THÔNG SỐ

-x0 x
[ECM, P-1, P + 1] Sử dụng x (số nguyên có độ chính xác tùy ý hoặc số hữu tỉ) làm điểm ban đầu. Vì
thí dụ, -x0 1/3 là hợp lệ. Nếu không được đưa ra, x được tạo từ giá trị sigma cho ECM,
hoặc ngẫu nhiên cho P-1 và P + 1.

-sigma s
[ECM] Sử dụng s (số nguyên có độ chính xác tùy ý) làm trình tạo đường cong. Nếu bỏ qua, s is
được tạo ra một cách ngẫu nhiên.

-A a
[ECM] Sử dụng a (số nguyên chính xác tùy ý) làm tham số đường cong. Nếu bỏ qua, nó có
được tạo ra từ giá trị sigma.

-đi val
[ECM, P-1, P + 1] Nhân điểm ban đầu với val, có thể là bất kỳ biểu thức hợp lệ nào,
có thể chứa ký tự đặc biệt N làm nơi giữ chỗ cho đầu vào hiện tại
con số. Thí dụ:

ecm -pp1 -go "N ^ 2-1" 1e6 <composite2000

STEP 2 THÔNG SỐ

-k k
[ECM, P-1, P + 1] Thực hiện k các khối ở bước 2. Đối với B2 giá trị, ngày càng tăng k
giảm mức sử dụng bộ nhớ của bước 2, với chi phí tốn nhiều thời gian hơn cho cpu.

-tập tin cây hồ sơ
Lưu trữ một số bảng dữ liệu trong tệp đĩa để giảm dung lượng bộ nhớ bị chiếm
bước 2, với chi phí của I / O đĩa. Dữ liệu sẽ được ghi vào tệp hồ sơ.1, hồ sơ.2, v.v.
Không hoạt động với giai đoạn nhanh 2 cho P + 1 và P-1.

-Điện n
[ECM, P-1] Sử dụng x ^n cho phần mở rộng của Brent-Suyama (-Điện 1 vô hiệu hóa Brent-Suyama's
gia hạn). Đa thức mặc định được chọn tùy thuộc vào phương thức và B2. Đối với P-1
và P + 1, tắt giai đoạn nhanh 2. Đối với P-1, n phải đều.

-dickson n
[ECM, P-1] Sử dụng độ-n Đa thức của Dickson cho phần mở rộng của Brent-Suyama. Đối với P-1 và
P + 1, tắt giai đoạn nhanh 2. Thích cho -Điện, n phải là thậm chí đối với P-1.

-tối đa n
Sử dụng nhiều nhất n megabyte bộ nhớ trong giai đoạn 2.

-ntt, -không-ntt
Bật hoặc tắt mã Biến đổi Số-Lý thuyết cho số học đa thức trong
giai đoạn 2. Với NTT, dF được chọn là lũy thừa của 2 và bị giới hạn bởi số
các số nguyên tố phù hợp vừa với một từ máy (đây là một hạn chế chỉ đối với 32 bit
hệ thống). Biến thể -no-ntt sử dụng nhiều bộ nhớ hơn, nhưng nhanh hơn NTT với
số đầu vào. Theo mặc định, NTT được sử dụng cho P-1, P + 1 và cho ECM với số lượng kích thước tại
nhất 30 từ máy.

OUTPUT

-q
Chế độ yên lặng. Các thừa số tìm thấy được in trên đầu ra tiêu chuẩn, với các hệ số
được phân tách bằng khoảng trắng, một dòng cho mỗi số đầu vào (nếu không tìm thấy hệ số,
số đầu vào chỉ được sao chép).

-v
Chế độ chi tiết. Nhiều thông tin được in ra, hơn thế nữa -v các tùy chọn làm tăng tính chi tiết. Với
một -v, loại phép nhân mô-đun được sử dụng, giá trị x0 ban đầu, tham số bước 2
và tiến độ cũng như các đường cong dự kiến ​​và thời gian để tìm các yếu tố có kích thước khác nhau cho ECM
được in. Với -v -v, giá trị A cho ECM và phần còn lại ở cuối bước 1 và
bước 2 được in. Hơn -v in dữ liệu nội bộ để gỡ lỗi.

-dấu thời gian
In dấu thời gian bất cứ khi nào đường cong ECM mới hoặc quá trình chạy P + 1 hoặc P-1 được xử lý.

HIỆN ĐẠI MÔN SỐ HỌC LỰA CHỌN

Một số thuật toán có sẵn cho phép nhân mô-đun. Chương trình cố gắng tìm
tốt nhất cho mỗi đầu vào; người ta có thể buộc một phương thức nhất định với các tùy chọn sau.

-mpzmod
Sử dụng hàm mpz_mod của GMP (bậc hai phụ cho các đầu vào lớn, nhưng gây ra một số chi phí
cho những người nhỏ).

-modmuln
Sử dụng phép nhân của Montgomery (phiên bản bậc hai). Thường là phương pháp tốt nhất cho nhỏ
đầu vào.

-redc
Sử dụng phép nhân của Montgomery (phiên bản bậc hai). Về mặt lý thuyết là tối ưu cho
đầu vào lớn.

-nobase2
Tắt mã cơ số 2 đặc biệt (được sử dụng khi số đầu vào là hệ số lớn của
2 ^ n + 1 hoặc 2 ^ n-1, xem -v).

-cơ sở2 n
Buộc sử dụng mã cơ số 2 đặc biệt, số đầu vào phải chia 2 ^n+1 nếu n > 0 hoặc 2 ^ |n| -1
if n <0.

FILE I / O

Các tùy chọn sau cho phép một người thực hiện bước 1 và bước 2 riêng biệt, hoặc bật
các máy khác nhau, vào các thời điểm khác nhau hoặc sử dụng phần mềm khác nhau (đặc biệt, George
Chương trình Prime95 / mprime của Woltman có thể tạo ra đầu ra bước 1 phù hợp để tiếp tục với
GMP-ECM). Nó cũng có thể hữu ích khi chia bước 2 thành nhiều lần chạy, bằng cách sử dụng B2min-B2max
tùy chọn.

-inp hồ sơ
Lấy đầu vào từ tệp hồ sơ thay vì từ đầu vào tiêu chuẩn.

-cứu hồ sơ
Lưu kết quả của bước 1 trong hồ sơ. Nếu hồ sơ tồn tại, một lỗi được đưa ra. Ví dụ: để thực hiện
chỉ bước 1 với B1= 1000000 trên số tổng hợp trong tệp "c155" và lưu nó
kết quả là tệp "foo", sử dụng

ecm -save foo 1e6 1 <c155

-savea hồ sơ
Như -cứu, nhưng gắn vào các tệp hiện có.

-sơ yếu lý lịch hồ sơ
Tiếp tục dư lượng từ hồ sơ, đọc từ đầu vào chuẩn nếu hồ sơ Là "-". Ví dụ: to
thực hiện bước 2 theo bước tính toán bước 1 ở trên, sử dụng

ecm -sơ yếu lý lịch foo 1e6

-chkpoint hồ sơ
Định kỳ ghi lượng dư hiện tại trong giai đoạn 1 vào hồ sơ. Trong trường hợp mất điện,
vv, quá trình tính toán có thể được tiếp tục với -sơ yếu lý lịch tùy chọn.

ecm -chkpnt foo -pm1 1e10 <largenumber.txt

LOOP PHƯƠNG THỨC

“Chế độ vòng lặp” (tùy chọn -c n) cho phép người ta chạy một số đường cong trên mỗi số đầu vào. Các
các tùy chọn sau kiểm soát hành vi của nó.

-c n
Thực hiện n chạy trên mỗi số đầu vào (mặc định là một). Tùy chọn này chủ yếu hữu ích cho
P + 1 (ví dụ với n= 3) hoặc đối với ECM, trong đó n có thể được đặt thành số lượng dự kiến ​​là
đường cong để tìm thừa số d với giới hạn bước 1 cho trước. Tùy chọn này không tương thích
với -bản tóm tắt, -sigma, -x0. Bố thí -c 0 tạo ra một vòng lặp vô hạn cho đến khi một hệ số là
tìm.

-một
Trong chế độ vòng lặp, dừng khi tìm thấy một yếu tố; mặc định là tiếp tục cho đến khi
cofactor là số nguyên tố hoặc số lần chạy được chỉ định được thực hiện.

-b
Xử lý đầu tiên theo chiều rộng: trong chế độ vòng lặp, chạy một đường cong cho mỗi số đầu vào, sau đó chạy một
đường cong thứ hai cho từng đường cong, v.v. Đây là chế độ mặc định với -inp.

-d
Xử lý theo chiều sâu: ở chế độ vòng lặp, chạy n đường cong cho số đầu tiên, sau đó n đường cong
cho cái thứ hai, v.v. Đây là chế độ mặc định với đầu vào tiêu chuẩn.

-đã n
Ở chế độ vòng lặp, trong lần chạy thứ hai và sau, chỉ xuất các biểu thức có tại
hầu hết n nhân vật. Mặc định là -đã 0.

-i n
Trong chế độ vòng lặp, tăng B1 by n sau mỗi đường cong.

-I n
Trong chế độ vòng lặp, nhân B1 bởi một yếu tố phụ thuộc vào n sau mỗi đường cong. Mặc định là một
cái này sẽ tối ưu trên một máy, trong khi -I 10 có thể được sử dụng khi cố gắng
nhân cùng một số đồng thời trên 10 máy giống nhau.

SHELL COMMAND CHẤP HÀNH

Các tùy chọn này cho phép thực hiện các lệnh shell để bổ sung chức năng cho GMP-ECM.

-ppccmd cmd
Thực thi lệnh cmd để kiểm tra tính nguyên thủy nếu các yếu tố và đồng yếu tố thay vì GMP-ECM's
các chức năng riêng. Số cần kiểm tra được chuyển qua stdin. Mã thoát 0 là
được hiểu là "có thể là số nguyên tố", một mã thoát khác XNUMX là "tổng hợp".

-faccmd cmd
Thực thi lệnh cmd bất cứ khi nào một yếu tố được tìm thấy bởi P-1, P + 1 hoặc ECM. Số đầu vào,
yếu tố và cofactor được chuyển qua stdin, mỗi yếu tố trên một dòng. Điều này có thể được sử dụng tức là để
gửi thư các nhân tố mới tự động:

ecm -faccmd 'mail -s “$ HOSTNAME đã tìm thấy một yếu tố”
[email được bảo vệ]'11e6 <cunningham.in

-idlecmd cmd
Thực thi lệnh cmd trước mỗi đường cong ECM, lần thử P-1 hoặc P + 1 trên một số được bắt đầu.
Nếu trạng thái thoát của cmd khác XNUMX, GMP-ECM chấm dứt ngay lập tức, nếu không
tiếp tục bình thường. GMP-ECM bị dừng trong khi cmd chạy, đưa ra một cách để cho phép
Ví dụ: ngủ GMP-ECM trong khi hệ thống đang bận.

KHÁC

-n
Chạy chương trình ở chế độ "đẹp" (dưới mức ưu tiên bình thường).

-nn
Chạy chương trình ở chế độ "rất đẹp" (ưu tiên nhàn rỗi).

-Tỷ lệ B2 f
Nhân giới hạn bước 2 mặc định B2 bằng giá trị dấu phẩy động f. Thí dụ: -Tỷ lệ B2
0.5 chia mặc định B2 bởi 2.

-giai đoạn1 thời gian n
Thêm n giây đến giai đoạn 1 lần. Điều này rất hữu ích để có được thời gian dự kiến ​​chính xác với -v if
một phần của giai đoạn 1 đã được thực hiện trong một lần chạy khác.

-cofdec
Buộc đầu ra cofactor ở dạng thập phân (ngay cả khi các biểu thức được sử dụng).

-h, --Cứu giúp
Hiển thị mô tả ngắn gọn về cách sử dụng ecm, các thông số và các tùy chọn dòng lệnh.

-printconfig
In các thông số cấu hình được sử dụng cho quá trình biên dịch và thoát.

ĐẦU VÀO TỔNG HỢP

Các số đầu vào có thể có một số dạng:

Các số thập phân thô như 123456789.

Nhận xét có thể được đặt trong tệp: mọi thứ sau “//” đều bị bỏ qua, cho đến cuối
hàng.

Sự tiếp nối dòng. Nếu một dòng kết thúc bằng một ký tự gạch chéo ngược “\”, nó được coi là
tiếp tục ở dòng tiếp theo.

Có thể sử dụng các biểu thức số học thông thường. Thí dụ: 3 * 5 + 2 ^ 10.

Giai thừa: ví dụ 53!.

Đa giai thừa: ví dụ 15! 3 means 15*12*9*6*3.

Primorial: ví dụ 11 # means 2*3*5*7*11.

Giảm sơ cấp: ví dụ 17 # 5 means 5*7*11*13*17.

Chức năng: hiện tại, chức năng khả dụng duy nhất là Phi (x, n).

EXIT TÌNH TRẠNG

Trạng thái thoát phản ánh kết quả của đường cong ECM cuối cùng hoặc P-1 / P + 1 lần thử chương trình
đã thực hiện. Các bit riêng lẻ biểu thị các sự kiện cụ thể, cụ thể:

bit 0
0 nếu kết thúc chương trình bình thường, 1 nếu xảy ra lỗi

bit 1
0 nếu không tìm thấy hệ số thích hợp, 1 nếu không

bit 2
0 nếu thừa số là hỗn hợp, 1 nếu thừa số là một số nguyên tố có thể xảy ra

bit 3
0 nếu cofactor là hỗn hợp, 1 nếu cofactor là một số nguyên tố có thể xảy ra

Do đó, các giá trị trạng thái thoát sau có thể xảy ra:

0
Kết thúc chương trình bình thường, không tìm thấy yếu tố nào

1
lỗi

2
Yếu tố tổng hợp được tìm thấy, đồng yếu tố là tổng hợp

6
Đã tìm thấy thừa số nguyên tố có thể xảy ra, đồng yếu tố là hỗn hợp

8
Đã tìm thấy số đầu vào

10
Hệ số tổng hợp được tìm thấy, đồng yếu tố là một số nguyên tố có thể xảy ra

14
Đã tìm thấy thừa số nguyên tố có thể xảy ra, đồng yếu tố là một số nguyên tố có thể xảy ra

Sử dụng ecm trực tuyến bằng dịch vụ onworks.net