ecm - تجزیه
اعداد صحیح
با استفاده
از روش‌های
ECM، P-1 یا P+1
ecm
[گزینه‌ها]
B1 [B2min-B2max | B2]
برنامه ecm
ابزاری
برای تجزیه
اعداد صحیح
به عوامل
اول با
استفاده از
روش خم
بیضوی (ECM)،
روش P-1، یا
روش P+1 است.
بخش‌های
بعدی
پارامترهای
مربوط به
این
الگوریتم‌ها
را شرح
می‌دهند.
B1
B1 کران
مرحله ۱ است.
این یک
پارامتر
اجباری است.
این مقدار
را می‌توان
در قالب عدد
صحیح (برای
مثال 3000000) یا در
قالب ممیز
شناور (3000000.0 یا 3e6)
مشخص کرد.
بزرگ‌ترین
مقدار ممکن
برای B1
برابر با 9007199254740996
برای P-1، و ULONG_MAX
یا 9007199254740996 (هر
کدام که
کوچک‌تر
باشد) برای ECM
و P+1 است. تمام
اعداد اول 2 <= p
<= B1 در مرحله
۱ پردازش
می‌شوند.
B2
B2 کران
مرحله ۲ است.
این
پارامتر
اختیاری
است: اگر
مشخص نشود،
یک مقدار
پیش‌فرض از
روی B1
محاسبه
می‌شود که
باید نزدیک
به بهینه
باشد.
همانند B1،
می‌توان آن
را در قالب
عدد صحیح یا
ممیز شناور
مشخص کرد.
بزرگ‌ترین
مقدار ممکن
برای B2
تقریباً 9e23
است، اما در
صورت مشخص
کردن گزینه
-k، به تعداد
بلوک‌های k
بستگی دارد.
تمام اعداد
اول B1 <= p <= B2 در
مرحله ۲
پردازش
می‌شوند.
اگر B2 < B1
باشد، هیچ
مرحله ۲ای
انجام
نمی‌شود.
B2min-B2max
همچنین
می‌توان از
قالب
B2min-
B2max
استفاده
کرد، بدین
معنا که
تمام اعداد
اول
B2min <= p <=
B2max
باید
پردازش
شوند.
بنابراین
مشخص کردن
تنها
B2
معادل
B1-
B2
است. مقادیر
B2min و
B2max
می‌توانند
به میزان
دلخواه
بزرگ
باشند، اما
با توجه به
تعداد
بلوک‌های
k، اختلاف
آن‌ها
نباید
تقریباً از 9e23
فراتر رود.
-pm1
اجرای P-1
به جای روش
پیش‌فرض (ECM).
-pp1
اجرای P+1
به جای روش
پیش‌فرض (ECM).
-x0 x
[ECM, P-1, P+1]
استفاده از
x (عدد صحیح
یا گویای با
دقت دلخواه)
به عنوان
نقطه اولیه.
برای مثال،
-x0 1/3 معتبر
است. در صورت
مشخص نشدن،
x از مقدار
سیگما برای
ECM، یا به صورت
تصادفی
برای P-1 و P+1
تولید
می‌شود.
-sigma s
[ECM]
استفاده از
s (عدد صحیح
با دقت
دلخواه) به
عنوان مولد
منحنی. در
صورت حذف، s
به صورت
تصادفی
تولید
می‌شود.
-A a
[ECM]
استفاده از
a (عدد صحیح
با دقت
دلخواه) به
عنوان
پارامتر
منحنی. در
صورت حذف،
از مقدار
سیگما
تولید
می‌شود.
-go val
[ECM, P-1, P+1] ضرب
نقطه اولیه
در
val، که
می‌تواند
هر عبارت
معتبری
باشد، و
احتمالاً
نویسه ویژه N
را به عنوان
جای‌نگهدار
برای عدد
ورودی فعلی
دربرگیرد.
مثال:
ecm -pp1 -go "N^2-1" 1e6 < composite2000
-k k
[ECM, P-1, P+1] اجرای
k بلوک در
مرحله ۲.
برای یک
مقدار مشخص
از B2،
افزایش k
میزان مصرف
حافظه در
مرحله ۲ را
به بهای
زمان
پردازنده (CPU)
بیشتر کاهش
می‌دهد.
-treefile file
برخی
جدول‌های
داده را در
فایل‌های
دیسک ذخیره
می‌کند تا
مقدار
حافظه
اشغال‌شده
در مرحله ۲
را به بهای I/O
دیسک کاهش
دهد.
داده‌ها در
فایل‌های
file.1، file.2 و غیره
نوشته
خواهند شد.
با مرحله ۲
سریع برای P+1 و
P-1 کار
نمی‌کند.
-power n
[ECM]
استفاده از
x^n برای بسط
Brent-Suyama (-power 1 بسط Brent-Suyama
را غیرفعال
می‌کند).
چندجمله‌ای
پیش‌فرض
بسته به روش
و B2 انتخاب
می‌شود.
-dickson n
[ECM]
استفاده از
چندجمله‌ای
Dickson با درجه-n
برای بسط Brent-Suyama.
-maxmem n
استفاده
حداکثر از n
مگابایت
حافظه در
مرحله ۲.
-ntt, -no-ntt
فعال یا
غیرفعال
کردن کد
تبدیل
نظریه
اعداد (Number-Theoretic Transform)
برای
محاسبات
چندجمله‌ای
در مرحله ۲.
با NTT، مقدار dF
توانی از ۲
انتخاب
می‌شود، و
به تعداد
اعداد اول
مناسبی که
در یک کلمه
ماشین (machine word)
جای
می‌گیرند
محدود است
(که این فقط
در
سیستم‌های
۳۲ بیتی یک
محدودیت
محسوب
می‌شود).
نگارش
-no-ntt
حافظه
بیشتری
مصرف
می‌کند،
اما برای
اعداد
ورودی بزرگ
سریع‌تر از NTT
است. به‌طور
پیش‌فرض، NTT
برای P-1، P+1 و
برای ECM روی
اعدادی با
حداکثر
اندازه ۳۰
کلمه ماشین
استفاده
می‌شود.
-q
حالت
بی‌صدا.
تجزیه‌های
پیدا شده در
خروجی
استاندارد
چاپ
می‌شوند،
در حالی که
فاکتورها
با فاصله از
یکدیگر جدا
شده‌اند؛
یک خط برای
هر عدد
ورودی (اگر
عاملی یافت
نشود، خود
عدد ورودی
صرفاً کپی
می‌شود).
-v
حالت
پرگو.
اطلاعات
بیشتری چاپ
می‌شود؛
گزینه‌های
-v بیشتر،
میزان
جزئیات
خروجی را
افزایش
می‌دهند. با
یک -v، نوع
ضرب
پیمانه‌ای
استفاده‌شده،
مقدار
اولیه x0،
پارامترها
و پیشرفت
گام ۲، و
منحنی‌ها و
زمان مورد
انتظار
برای یافتن
عامل‌هایی
با
اندازه‌های
مختلف در ECM
چاپ
می‌شوند. با
-v -v، مقدار A
برای ECM و
باقی‌مانده‌ها
در پایان
گام ۱ و گام ۲
چاپ
می‌شوند.
تعداد -v
بیشتر،
داده‌های
داخلی را
برای
اشکال‌زدایی
چاپ
می‌کند.
-timestamp
هربار که
یک منحنی ECM
جدید یا یک
اجرای P+1 یا P-1
پردازش
می‌شود، یک
برچسب
زمانی چاپ
می‌کند.
الگوریتم‌های
متعددی
برای ضرب
پیمانه‌ای
در دسترس
هستند.
برنامه
تلاش
می‌کند
بهترین
مورد را
برای هر
ورودی پیدا
کند؛
می‌توان با
گزینه‌های
زیر
استفاده از
یک روش مشخص
را اجبار
کرد.
-mpzmod
استفاده
از تابع mpz_mod
کتابخانه GMP
(برای
ورودی‌های
بزرگ از
مرتبه
زیر-مربعی
است، اما
برای
ورودی‌های
کوچک
مقداری
سربار
ایجاد
می‌کند).
-modmuln
استفاده
از ضرب
مونتگومری
(نسخه درجه
دو). معمولاً
بهترین روش
برای
ورودی‌های
کوچک است.
-redc
استفاده
از ضرب
مونتگومری
(نسخه
زیر-مربعی).
از نظر
تئوری برای
ورودی‌های
بزرگ بهینه
است.
-nobase2
غیرفعال
کردن کد
ویژه مبنای
۲ (که وقتی
عدد ورودی
عامل بزرگی
از 2^n+1 یا 2^n-1 باشد
استفاده
می‌شود، -v
را ببینید).
-base2 n
اجبار به
استفاده از
کد ویژه
مبنای ۲؛ در
صورتی که n > 0
باشد، عدد
ورودی باید
مقسوم‌علیه
2^n+1 باشد، یا
اگر n < 0
باشد،
مقسوم‌علیه
2^|n|-1 باشد.
گزینه‌های
زیر امکان
انجام گام ۱
و گام ۲ را به
صورت
جداگانه
فراهم
می‌کنند،
خواه روی
رایانه‌های
مختلف، در
زمان‌های
مختلف، یا
با استفاده
از
نرم‌افزارهای
مختلف (به
ویژه،
برنامه Prime95/mprime
جورج ولتمن
می‌تواند
خروجی گام ۱
مناسب برای
از سرگیری
با GMP-ECM را
تولید کند).
همچنین
تقسیم گام ۲
به چند اجرا
با استفاده
از گزینه B2min-B2max
می‌تواند
مفید باشد.
-inp file
خواندن
ورودی از
فایل file به
جای ورودی
استاندارد.
-save file
ذخیره
نتیجه گام ۱
در
file. اگر
file
وجود داشته
باشد، یک
خطا ایجاد
می‌شود.
مثال: برای
اجرای تنها
گام ۱ با
B1=1000000
روی عدد
مرکب موجود
در فایل "c155" و
ذخیره
نتیجه آن در
فایل "foo"،
استفاده
کنید از:
ecm -save foo 1e6 1 < c155
-savea file
مانند
-save، اما به
انتهای
فایل‌های
موجود
الحاق
می‌کند.
-resume file
از
سرگیری
باقی‌مانده‌ها
از
file؛ در
صورتی که
file
برابر با "-"
باشد، از
ورودی
استاندارد
می‌خواند.
مثال: برای
انجام گام ۲
در ادامه
محاسبه گام
۱ فوق،
استفاده
کنید از:
-chkpoint file
نوشتن
دوره‌ای
باقی‌مانده
فعلی در
مرحله ۱ در
file. در صورت
قطعی برق و
غیره،
محاسبه
می‌تواند
با گزینه
-resume
ادامه یابد.
ecm -chkpnt foo -pm1 1e10 < largenumber.txt
“حالت
حلقه”
(گزینهٔ -c n)
امکان
اجرای
چندین
منحنی را
روی هر عدد
ورودی
فراهم
می‌کند.
گزینه‌های
زیر رفتار
آن را کنترل
می‌کنند.
-c n
اجرای n
بار روی هر
عدد ورودی
(پیش‌فرض یک
است). این
گزینه
عمدتاً
برای P+1 (برای
مثال با n=3) یا
برای ECM مفید
است، جایی
که می‌توان
n را بر روی
تعداد
منحنی‌های
مورد
انتظار
برای یافتن
یک عامل
d-رقمی با
کران
مرحلهٔ ۱
مشخص تنظیم
کرد. این
گزینه با -resume, -sigma,
-x0 ناسازگار
است. دادن -c 0
یک حلقهٔ
بی‌پایان
تا زمان
پیدا شدن یک
عامل ایجاد
می‌کند.
-one
در حالت
حلقه، با
پیدا شدن یک
عامل متوقف
می‌شود؛
حالت
پیش‌فرض
ادامه دادن
تا زمانی
است که
هم‌عامل (cofactor)
اول باشد یا
تعداد
دفعات
اجرای
مشخص‌شده
به پایان
برسد.
-b
پردازش
اول‌سطح (Breadth-first):
در حالت
حلقه، برای
هر عدد
ورودی یک
منحنی اجرا
می‌شود،
سپس یک
منحنی دوم
برای هر
کدام و به
همین ترتیب.
این حالت
پیش‌فرض
هنگام
استفاده از
-inp است.
-d
پردازش
اول‌عمق (Depth-first):
در حالت
حلقه،
ابتدا n
منحنی برای
اولین عدد،
سپس n منحنی
برای دومین
عدد و به
همین ترتیب
اجرا
می‌شود. این
حالت
پیش‌فرض
هنگام
استفاده از
ورودی
استاندارد
است.
-ve n
در حالت
حلقه، در
اجرای دوم و
دفعات پس از
آن، تنها
عبارت‌هایی
را در خروجی
نمایش
می‌دهد که
حداکثر n
نویسه
داشته
باشند.
مقدار
پیش‌فرض -ve 0
است.
-i n
در حالت
حلقه،
مقدار B1 را
پس از هر
منحنی به
اندازهٔ n
افزایش
می‌دهد.
-I n
در حالت
حلقه،
مقدار B1 را
پس از هر
منحنی در
ضریبی
وابسته به n
ضرب می‌کند.
مقدار
پیش‌فرض یک
است که روی
یک سیستم
بهینه
خواهد بود،
در حالی که
می‌توان از
-I 10 هنگام
تلاش برای
تجزیهٔ
هم‌زمان یک
عدد روی ۱۰
سیستم
یکسان
استفاده
کرد.
این
گزینه‌ها
امکان
اجرای
دستورات
پوسته را
برای گسترش
قابلیت‌های
GMP-ECM فراهم
می‌کنند.
-prpcmd cmd
دستور cmd
را به جای
توابع
درونی خود GMP-ECM
برای
آزمودن اول
بودن
عامل‌ها و
هم‌عامل‌ها
اجرا
می‌کند. عدد
مورد
آزمایش از
طریق stdin
ارسال
می‌شود. کد
خروج 0 به
عنوان
“احتمالاً
اول” (probably prime) و کد
خروج غیر
صفر به
عنوان
“مرکب” (composite)
تفسیر
می‌شود.
-faccmd cmd
هر زمان
عاملی توسط P-1
،P+1 یا ECM پیدا
شود، دستور
cmd را اجرا
می‌کند. عدد
ورودی،
عامل و
هم‌عامل هر
کدام در یک
خط از طریق stdin
فرستاده
می‌شوند. از
این گزینه
می‌توان
برای مثال
جهت ارسال
خودکار
عامل‌های
جدید با
ایمیل
استفاده
کرد:
ecm -faccmd 'mail -s “$HOSTNAME found a factor”
me@myaddress.com' 11e6 < cunningham.in
-idlecmd cmd
دستور
cmd
را پیش از
شروع هر
منحنی ECM یا هر
تلاش P-1 یا P+1
روی یک عدد
اجرا
می‌کند. اگر
وضعیت خروج
cmd غیر صفر
باشد، GMP-ECM
فوراً
خاتمه
می‌یابد؛
در غیر این
صورت به طور
عادی ادامه
می‌دهد. در
هنگام
اجرای
cmd،
برنامهٔ GMP-ECM
متوقف
می‌شود؛
این
سازوکار
راهکاری
ارائه
می‌دهد تا
مثلاً در
هنگام شلوغ
بودن سیستم
بتوان GMP-ECM را
به حالت
خواب
درآورد.
-n
اجرای
برنامه در
حالت “nice”
(اولویت
کمتر از
حالت عادی).
-nn
اجرای
برنامه در
حالت “very nice”
(اولویت
بی‌کار یا idle).
-B2scale f
ضرب کردن
کران
پیش‌فرض
مرحله ۲ B2 در
مقدار ممیز
شناور f.
مثال: -B2scale 0.5
مقدار
پیش‌فرض B2
را بر ۲
تقسیم
می‌کند.
-stage1time n
افزودن n
ثانیه به
زمان مرحله
۱. این گزینه
برای به دست
آوردن زمان
مورد
انتظار
دقیق با -v در
صورتی که
بخشی از
مرحله ۱ در
اجرای
دیگری
انجام شده
باشد، مفید
است.
-cofdec
اجبار
خروجی
کوفاکتور
به صورت
ده‌دهی (حتی
در صورت
استفاده از
عبارات
محاسباتی).
-h, --help
نمایش
توضیحی
کوتاه از
نحوه
استفاده ecm،
پارامترها
و
گزینه‌های
خط فرمان.
-printconfig
چاپ
پارامترهای
پیکربندی
استفاده‌شده
برای
کامپایل و
خروج از
برنامه.
اعداد
ورودی
می‌توانند
چندین حالت
داشته
باشند:
اعداد
ده‌دهی خام
مانند 123456789.
می‌توان
در فایل از
کامنت
استفاده
کرد: همه چیز
بعد از “//”
تا انتهای
خط نادیده
گرفته
می‌شود.
ادامه خط.
اگر خطی به
نویسه
بک‌اسلش “\”
ختم شود،
ادامه‌دار
در نظر
گرفته شده و
در خط بعدی
دنبال
می‌شود.
می‌توان
از عبارات
محاسباتی
رایج
استفاده
کرد. مثال:
3*5+(2+7)^10.
فاکتوریل:
مثال 53!.
چندفاکتوریل:
برای مثال
15!3 به معنی 15*12*9*6*3
است.
پریموریل
(Primorial): برای
مثال 11# به
معنی 2*3*5*7*11 است.
پریموریل
کاهش‌یافته:
برای مثال
17#5 به معنی 5*7*11*13*17
است.
توابع:
GCD(a,b):
بزرگ‌ترین
مقسوم‌علیه
مشترک
مثال: GCD(120,28) = 4
Phi(n,x): n-امین
چندجمله‌ای
دایره‌بر
(سیکلوتومیک)
محاسبه‌شده
در x
مثال: Phi(3,5) = 1 + x + x^2
= 31
وضعیت
خروج،
نتیجه
آخرین
منحنی ECM یا
تلاش P-1/P+1
انجام‌شده
توسط
برنامه را
نشان
می‌دهد.
بیت‌های
منفرد
نشان‌دهنده
رویدادهای
مشخصی
هستند،
به‌ویژه:
بیت 0
0 در صورت
پایان عادی
برنامه، 1 در
صورت وقوع
خطا
بیت 1
0 اگر هیچ
عامل
سره‌ای
یافت نشد، 1
در غیر این
صورت
بیت 2
0 اگر
عامل مرکب
باشد، 1 اگر
عامل
احتمالاً
اول باشد
بیت 3
0 اگر
هم‌عامل
مرکب باشد، 1
اگر
هم‌عامل
احتمالاً
اول باشد
بنابراین،
مقادیر
وضعیت خروج
زیر ممکن
است رخ
دهند:
0
خاتمه
عادی
برنامه،
هیچ عاملی
یافت نشد
1
خطا
2
عامل
مرکب یافت
شد،
هم‌عامل
مرکب است
6
عامل
احتمالاً
اول یافت
شد،
هم‌عامل
مرکب است
8
عدد
ورودی یافت
شد
10
عامل
مرکب یافت
شد،
هم‌عامل
احتمالاً
اول است
14
عامل
احتمالاً
اول یافت
شد،
هم‌عامل
احتمالاً
اول است
Pierrick Gaudry <gaudry at lix dot polytechnique dot fr>
کد اسمبلی
کارآمدی
برای mul/redc
ترکیبی
ارائه کرده
است؛
Jim Fougeron <jfoug at cox dot net> در
نوشتن
تجزیه‌کننده
عبارت و
چندین
گزینه خط
فرمان
مشارکت
داشته
است؛
Laurent Fousse <laurent at komite dot net> در
نوشتن کد
ضرب میانی (middle
product) و
ابزارهای
autoconf/automake مشارکت
داشته و
نگه‌دارنده
بسته Debian است؛
Alexander Kruppa <(lastname)al@loria.fr> در
برآورد
احتمال
موفقیت
برای ECM،
مرحله دوم
جدید P+1 و P-1 (به
همراه P.-L. Montgomery)،
کد جدید
اسمبلی AMD64
برای mulredc و
برخی موارد
دیگر
مشارکت
داشته
است؛
Dave Newman <david.(lastname)@jesus.ox.ac.uk>
کد ضرب Kronecker-Schoenhage و NTT
را ارائه
کرده است؛
Jason S. Papadopoulos در
افزایش
سرعت کد NTT
مشارکت
داشته است
Paul Zimmermann <zimmerma at loria dot fr>
نویسنده
نسخه نخست
برنامه و
نگه‌دارنده
اصلی GMP-ECM است.
نکته:
نشانی‌های
ایمیل
مبهم‌سازی
شده‌اند،
جایگزینی‌های
لازم باید
آشکار
باشند.
