ecm - מקוון בענן

תָכְנִית:

שֵׁם

ecm - פירוק מספרים שלמים באמצעות ECM, P-1 או P+1

תַקצִיר

ecm [אפשרויות] B1 [B2min-B2max | B2]

תיאור

ecm היא תוכנית הפקת מספרים שלמים המשתמשת בשיטת עקומה אליפטית (ECM), שיטת P-1,
או שיטת P+1. הסעיפים הבאים מתארים פרמטרים רלוונטיים לאלה
אלגוריתמים.

שלב 1 ו שלב 2 כָּרוּך פרמטרים

B1
B1 הוא שלב 1 קשור. זה פרמטר חובה. ניתן לתת אותו במספר שלם
פורמט (לדוגמה 3000000) או בפורמט של נקודה צפה (3000000.0 או 3e6). ה
הכי גדול שאפשר B1 הערך הוא 9007199254740996 עבור P-1, ו-ULONG_MAX או
9007199254740996 (הקטן מביניהם) עבור ECM ו-P+1. כל ראשוני 2 <= p <= B1 יש לו
מעובד בשלב 1.

B2
B2 הוא שלב 2 קשור. זה אופציונלי: אם מושמט, ערך ברירת מחדל מחושב
B1, שאמור להיות קרוב לאופטימלי. כמו B1, ניתן לתת אותו במספר שלם או ב
פורמט נקודה צפה. הערך הגדול ביותר האפשרי של B2 הוא בערך 9e23, אבל
תלוי במספר הבלוקים k אם אתה מציין את -k אוֹפְּצִיָה. הכל ראשוני B1 <= p <=
B2 מעובדים בשלב 2. אם B2 < B1, לא מבוצע שלב 2.

B2min-B2max
לחלופין ניתן להשתמש ב- B2min-B2max טופס, כלומר כל ראשוני B2min <= p
<= B2max צריך לעבד. כך מפרט B2 מתאים רק ל B1-B2. הערכים
of B2min ו B2max יכול להיות גדול באופן שרירותי, אבל ההפרש שלהם לא יעלה
בערך 9e23, בכפוף למספר הבלוקים k.

FACTORING שיטה

-pm1
בצע P-1 במקום שיטת ברירת המחדל (ECM).

-עמוד1
בצע P+1 במקום שיטת ברירת המחדל (ECM).

קבוצה ו התחלתי נקודה פרמטרים

-x0 x
[ECM, P-1, P+1] השתמש x (מספר שלם או רציונלי בדיוק שרירותי) כנקודה התחלתית. ל
דוגמא, -x0 1/3 תקף. אם לא ניתן, x נוצר מערך הסיגמא עבור ECM,
או באופן אקראי עבור P-1 ו-P+1.

-סיגמה s
[ECM] השתמש s (מספר שלם בדיוק שרירותי) כמחולל עקומה. אם מושמט, s is
נוצר באקראי.

-A a
[ECM] השתמש a (מספר שלם בדיוק שרירותי) כפרמטר עקומה. אם מושמט, נכון
נוצר מערך הסיגמא.

-ללכת val
[ECM, P-1, P+1] הכפל את הנקודה ההתחלתית ב val, אשר יכול כל ביטוי חוקי,
אולי מכיל את התו המיוחד N כמחזיק מקום עבור הקלט הנוכחי
מספר. דוגמא:

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

שלב 2 פרמטרים

-k k
[ECM, P-1, P+1] בצע k בלוקים בשלב 2. נתון B2 ערך, עולה k
מקטין את השימוש בזיכרון של שלב 2, על חשבון יותר זמן מעבד.

-קובץ עץ פילה
מאחסן כמה טבלאות נתונים בקבצי דיסק כדי להפחית את כמות הזיכרון התפוסה
שלב 2, על חשבון קלט/פלט דיסק. הנתונים ייכתבו לקבצים פילה.1, פילה.2 וכו '.
לא עובד עם שלב 2 מהיר עבור P+1 ו-P-1.

צריכת חשמל n
[ECM, P-1] השתמש ב-x^n להרחבה של ברנט-סויאמה (צריכת חשמל 1 משבית את זה של ברנט-סויאמה
סיומת). פולינום ברירת המחדל נבחר בהתאם לשיטה ול-B2. עבור P-1
ו-P+1, משבית את שלב 2 המהיר. עבור P-1, n חייב להיות אחיד.

-דיקסון n
[ECM, P-1] השתמש בדרגה-n הפולינום של דיקסון עבור הרחבה של ברנט-סויאמה. עבור P-1 ו
P+1, משבית את שלב 2 המהיר. לייק עבור צריכת חשמל, n חייב להיות זוגי עבור P-1.

-maxmem n
השתמש לכל היותר n מגה-בייט של זיכרון בשלב 2.

-ntt, -לא-ntt
הפעל או השבת את קוד הטרנספורמציה מספר תיאורטית עבור אריתמטיקה פולינומית ב
שלב 2. עם NTT, dF נבחר להיות בחזקת 2, והוא מוגבל במספר
ראשוניים מתאימים המתאימים למילת מכונה (שהיא מגבלה רק על 32 סיביות
מערכות). הגרסה -no-ntt משתמשת ביותר זיכרון, אך היא מהירה יותר מ-NTT עם large
הזנת מספרים. כברירת מחדל, NTT משמש עבור P-1, P+1 ועבור ECM במספרים בגודל ב
רוב 30 מילות המכונה.

תפוקה

-q
מצב שקט. הפקטוריזציות שנמצאו מודפסות על פלט סטנדרטי, עם גורמים
מופרדים ברווחים לבנים, שורה אחת לכל מספר קלט (אם לא נמצא גורם, ה-
מספר הקלט פשוט מועתק).

-v
מצב מילולי. מידע נוסף מודפס, עוד -v האפשרויות מגדילות את הדיבור. עם
אחד -v, סוג הכפל המודולרי שבו נעשה שימוש, ערך x0 התחלתי, פרמטרים של שלב 2
והתקדמות, ועקומות וזמן צפויים למציאת גורמים בגדלים שונים עבור ECM
מודפסים. עם -v -v, ערך A עבור ECM ושאריות בסוף שלב 1 ו
שלב 2 מודפסים. יותר -v להדפיס נתונים פנימיים לצורך איתור באגים.

-חותמת זמן
הדפס חותמת זמן בכל פעם שעקומת ECM חדשה או ריצת P+1 או P-1 מעובדת.

מודולרי חֶשְׁבּוֹן אפשרויות

מספר אלגוריתמים זמינים לכפל מודולרי. התוכנית מנסה למצוא את
הטוב ביותר עבור כל קלט; אפשר לכפות שיטה נתונה עם האפשרויות הבאות.

-mpzmod
השתמש בפונקציית mpz_mod של GMP (תת ריבועית עבור כניסות גדולות, אך מעוררת תקורה מסוימת
לקטנים).

-מודמולן
השתמש בכפל של מונטגומרי (גרסה ריבועית). בדרך כלל השיטה הטובה ביותר לקטנים
קֶלֶט.

-אדום
השתמש בכפל של מונטגומרי (גרסה תת-ריבועית). תיאורטית אופטימלי עבור
קלט גדול.

-nobase2
השבת קוד בסיס 2 מיוחד (שנעשה בו שימוש כאשר מספר הקלט הוא פקטור גדול של
2^n+1 או 2^n-1, ראה -v).

-בסיס2 n
לכפות שימוש בקוד בסיס 2 מיוחד, מספר הקלט חייב לחלק 2^n+1 אם n > 0, או 2^|n| -1
if n <0.

קובץ I / O

האפשרויות הבאות מאפשרות לאדם לבצע את שלב 1 ושלב 2 בנפרד, בכל אחד מהם
מכונות שונות, בזמנים שונים, או באמצעות תוכנות שונות (בפרט, ג'ורג'
תוכנית Prime95/mprime של Woltman יכולה לייצר פלט שלב 1 המתאים לחידוש
GMP-ECM). זה יכול להיות שימושי גם לפצל את שלב 2 למספר ריצות, באמצעות ה B2min-B2max
אוֹפְּצִיָה.

-inp פילה
קח קלט מהקובץ פילה במקום מקלט רגיל.

-לשמור פילה
שמור את התוצאה של שלב 1 ב פילה. אם פילה קיים, הועלתה שגיאה. דוגמה: לבצע
רק שלב 1 עם B1=1000000 במספר המשולב בקובץ "c155" ושמור אותו
התוצאה בקובץ "foo", השתמש

ecm -save foo 1e6 1 < c155

-סאווה פילה
כמו -לשמור, אך מוסיף לקבצים קיימים.

-קורות חיים פילה
המשך שאריות מ פילה, קורא מקלט סטנדרטי if פילה הוא "-". דוגמה: ל
בצע את שלב 2 בעקבות חישוב שלב 1 לעיל, השתמש

ecm -resume foo 1e6

-chkpoint פילה
כתוב מעת לעת את השאריות הנוכחיות בשלב 1 ל פילה. במקרה של הפסקת חשמל,
וכו', ניתן להמשיך את החישוב עם ה -קורות חיים אוֹפְּצִיָה.

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

לולאה MODE

"מצב הלולאה" (אפשרות -c n) מאפשר להריץ מספר עקומות על כל מספר קלט. ה
האפשרויות הבאות שולטות בהתנהגותו.

-c n
לְבַצֵעַ n פועל על כל מספר קלט (ברירת המחדל היא אחד). אפשרות זו שימושית בעיקר עבור
P+1 (לדוגמה עם n=3) או עבור ECM, איפה n ניתן להגדיר למספר הצפוי של
עקומות כדי למצוא גורם ד-ספרתי עם שלב נתון 1 מוגבל. אפשרות זו אינה תואמת
עם -קורות חיים, -סיגמה, -x0. מַתָן -c 0 מייצר לולאה אינסופית עד שגורם הוא
מצאתי.

-אחד
במצב לולאה, עצור כאשר נמצא גורם; ברירת המחדל היא להמשיך עד ל
cofactor הוא ראשוני או שבוצעו מספר הריצות שצוין.

-b
עיבוד רוחב ראשון: במצב לולאה, הפעל עקומה אחת עבור כל מספר קלט, ולאחר מכן א
עקומה שנייה לכל אחד, וכן הלאה. זהו מצב ברירת המחדל עם -inp.

-d
עיבוד עומק ראשון: במצב לולאה, הפעל n עקומות עבור המספר הראשון, אם כן n עקומות
עבור השני וכן הלאה. זהו מצב ברירת המחדל עם קלט סטנדרטי.

-ve n
במצב לולאה, בריצה השנייה ואחריה, פלט רק ביטויים שיש להם at
רוב n דמויות. ברירת המחדל היא -ve 0.

-i n
במצב לולאה, הגדל B1 by n אחרי כל עקומה.

-I n
במצב לולאה, הכפל B1 לפי גורם תלוי n אחרי כל עקומה. ברירת המחדל היא אחת
שאמור להיות אופטימלי במכונה אחת, בעוד -I 10 יכול לשמש כאשר מנסים
גורם למספר זהה בו זמנית ב-10 מכונות זהות.

SHELL פקודה ביצוע

אופטינים אלה מאפשרים ביצוע פקודות מעטפת כדי להשלים את הפונקציונליות ל-GMP-ECM.

-prpcmd cmd
בצע פקודה cmd לבדוק ראשוניות אם גורמים וקו-פקטורים במקום GMP-ECM's
פונקציות משלו. המספר לבדיקה מועבר דרך stdin. קוד יציאה של 0 הוא
מתפרש כ"כנראה ראשוני", קוד יציאה שאינו אפס כ"מרוכב".

-faccmd cmd
מבצע פקודה cmd בכל פעם שגורם נמצא על ידי P-1, P+1 או ECM. מספר הקלט,
הגורם והקופקטור מועברים דרך stdin, כל אחד על קו. זה יכול לשמש כלומר כדי
שלח גורמים חדשים אוטומטית:

ecm -faccmd 'mail -s "$HOSTNAME מצא גורם"
[מוגן בדוא"ל]' 11e6 < cunningham.in

-idlecmd cmd
מבצע פקודה cmd לפני כל עקומת ECM, מתחיל ניסיון P-1 או P+1 במספר.
אם מצב היציאה של cmd אינו אפס, GMP-ECM מסתיים באופן מיידי, אחרת הוא
ממשיך כרגיל. GMP-ECM מופסק בזמן cmd פועל, מציע דרך להשכרה
GMP-ECM שינה למשל בזמן שהמערכת תפוסה אחרת.

שונות

-n
הפעל את התוכנית במצב "נחמד" (מתחת לעדיפות רגילה).

-nn
הפעל את התוכנית במצב "נחמד מאוד" (עדיפות סרק).

סולם B2 f
הכפל את ברירת המחדל של שלב 2 קשור B2 לפי ערך הנקודה הצפה f. דוגמא: סולם B2
0.5 מחלק את ברירת המחדל B2 על ידי 2.

-זמן שלב 1 n
להוסיף n שניות לשלב 1 פעם אחת. זה שימושי כדי לקבל את הזמן הצפוי הנכון -v if
חלק משלב 1 נעשה בריצה נוספת.

-cofdec
לכפות פלט קו-פקטור בעשרוני (גם אם נעשה שימוש בביטויים).

-h, - עזרה
הצג תיאור קצר של שימוש ב-ecm, פרמטרים ואפשרויות שורת הפקודה.

-printconfig
מדפיס פרמטרים של תצורה המשמשים להידור וליציאות.

קלט תחביר

למספרי הקלט יכולים להיות מספר צורות:

מספרים עשרוניים גולמיים כמו 123456789.

ניתן להוסיף הערות בקובץ: מתעלמים מכל מה שאחרי "//", עד לסוף
קו.

המשך קו. אם שורה מסתיימת עם תו "\", היא נחשבת ל
להמשיך בשורה הבאה.

ניתן להשתמש בביטויים אריתמטיים נפוצים. דוגמא: 3*5+2^10.

פקטוריאלי: דוגמה 53!.

רב גורמים: דוגמה 15! 3 means 15*12*9*6*3.

ראשוני: דוגמה 11 # means 2*3*5*7*11.

ראשוני מופחת: דוגמה 17 # 5 means 5*7*11*13*17.

פונקציות: כרגע, הפונקציה הזמינה היחידה היא Phi(x,n).

יְצִיאָה סטָטוּס

מצב היציאה משקף את התוצאה של עקומת ה-ECM האחרונה או ניסיון P-1/P+1 של התוכנית
מְבוּצָע. ביטים בודדים מסמנים אירועים מסוימים, במיוחד:

ביט 0
0 אם סיום תוכנית רגיל, 1 אם אירעה שגיאה

ביט 1
0 אם לא נמצא גורם תקין, 1 אחרת

ביט 2
0 אם הגורם מורכב, 1 אם הגורם הוא ראשוני סביר

ביט 3
0 אם קו-פקטור מורכב, 1 אם קו-פקטור הוא ראשוני סביר

לפיכך, ערכי סטטוס היציאה הבאים עשויים להתרחש:

0
סיום תוכנית רגיל, לא נמצא גורם

1
שְׁגִיאָה

2
נמצא גורם מרוכב, גורם מרוכב הוא מרוכב

6
נמצא גורם ראשוני סביר, cofactor הוא מורכב

8
נמצא מספר קלט

10
נמצא גורם מורכב, קו-פקטור הוא ראשוני סביר

14
נמצא גורם ראשוני סביר, קופקטור הוא ראשוני סביר

השתמש ב-ecm באינטרנט באמצעות שירותי onworks.net