שיחה:מבחן לוקאס-להמר למספרי מרסן

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

מבחן ראשוניות מורחב

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

פסאודו-קוד של האלגוריתם:

• קלט - inp
• קבע n ל-${\frac {inp+1}{4}}$
• רשימות - L,N,O \ כאשר L היא $V_{2^{n}}(4,1)$ (סדרת לוקאס), O היא $V_{N_{n}}(4,1)$ ו-N היא סדרת מספרים טבעיים שמשתנה בין כל מספר למספר ועוזרת לחישוב. חשוב - L ו-O הן מודלו inp, כלומר, כשמכניסים אליהם מספר i לא מוכנס המספר עצמו, אלא $i\!\!\!\!\mod inp$ (אני יודע שזה לא מקובל, אבל זה פסאודו-קוד, מה אתם רוצים?)
• הוסף 4 ל-L \ מקום 0 - $V_{1}(4,1)=4$
• חזור $\lg(n)$ פעמים:
  • הוסף את L(length(L))^2-2 ל-L \ מחשב לפי הנוסחא $V_{2n}(P,Q)=V_{n}^{2}-2Q^{n}$
• קבע l ל-$\lg(n)$
• הכנס n במקום l ב-N
• קבע m ל-n
• חזור עד ש-m הוא חזקה של 2
  • קבע k ל-m-2^l
  • הכנס k במקום $\lg(k)$ ב-N
  • הכנס $2^{l}-k$ במקום $\lg(2^{l}-k)$
  • קבע l ל-l-1
  • קבע m ל-$N(l)$
• הכנס $V(l)$ במקום ה-l של O
• חזור עד ש-$l=\lg(n)$
  • קבע l ל-l+1
  • הכנס את $L(l)O\left(\lg \left(N(l)-2^{l}\right)\right)-O\left(\lg \left(2^{l+1}-N(l)\right)\right)$ במקום ה-l של O \ מחשב לפי הנוסחא $V_{n+m}(P,Q)=V_{n}(P,Q)V_{m}(P,Q)-Q^{n}V_{n-m}(P,Q)$
• אם O(l)=0 המספר ראשוני, אחרת המספר פריק

רוב האלגוריתם הוא חישוב $V_{n}(4,1)$.

אם אני לא טועה, גם לאלגוריתם הזה יש סיבוכיות של $\Theta (\log(n)^{3})$. רועי.ס - שיחה 09:12, 27 באוגוסט 2014 (IDT) (את כל הפסקא עד לכאן אני כתבתי)

יש לי הוכחה שאין התנגשות בהכנסה ל-N. זו הוכחה באינדוקציה. הנחת האינדוקציה - החזקות של 2, בהן האלגוריתם מסתיים ישר ולא מוכנסים עוד ערכים ל-N. צעד האינדוקציה - נניח שלכל המספרים הקטנים מ-m אין התנגשות, עכשיו, כשמגיעים ל-m מכניסים לרשימה שני מספרים - $k=m-2^{\lg(m)}$ ו-$j=2^{\lg(m)}-k$, נניח בלי הגבלת הכלליות ש-k הוא המקסימלי מביניהם. מכיוון ש-$k={\frac {k+k}{2}}\geq {\frac {k+j}{2}}={\frac {2^{\lg(m)}}{2}}=2^{\lg(n)-1}$ הוא מוכנס במקום ה-lg(m)-1, כלומר, עוברים עליו בצעד הבא. עכשיו מכיוון ש-k<m (הוא נוצר מחיסור של משהו או מ-m או ממספר קטן ממנו) פועלת עליו הנחת האינדוקציה, זאת אומרת שאין התנגשויות אחריו, עכשיו, בצעד הבא מגיעים ל-$i=k-2^{\lg(k)}$ ול-$2^{\lg(k)}-i=2^{\lg(k)}-(k-2^{\lg(k)})=2^{\lg(k)+1}-k=2^{\lg(m)-1+1}-k=2^{\lg(m)}-k=j$, מ.ש.ל. -- רועי.ס - שיחה 12:34, 27 באוגוסט 2014 (IDT)

יש בעיה באלגוריתם - אמנם הכיוון שמוצג בערך (שעל כל מספר ראשוני האלגוריתם יענה "ראשוני") עובד טוב גם לגביו, אך בכיוון השני יש מספרים בעייתיים (הקטן ביותר מביניהם הוא 1,037,623). ברצוני לדעת איך פועל הכיוון השני של ההוכחה ולמה הוא נופל אצלי אבל לא במספרי-מרסן.

דרך אגב, בפסאודו-קוד, lg מעוגל למטה (אני לא יודע איך זה בד"כ) (שכחתי לחתום על ההודעה הקודמת) -- רועי.ס - שיחה 13:55, 28 באוגוסט 2014 (IDT)

מה האלגוריתם הזה מחשב, מתמטית? עוזי ו. - שיחה 13:59, 28 באוגוסט 2014 (IDT)

הוא מחשב את $V_{\frac {n+1}{4}}(4,1)$ כאשר n הוא הקלט ו-$V(4,1)$ היא סדרת לוקאס המוגדרת ע"י נוסחת הנסיגה $V_{m}=4V_{m-1}-V_{m-2}$ ותנאי ההתחלה $V_{0}=2,V_{1}=4$ ומשווה אותו ל-0 -- רועי.ס - שיחה 14:35, 28 באוגוסט 2014 (IDT)

אופס התבלבלתי, האלגוריתם לא מחשב את $V_{\frac {n+1}{4}}(4,1)$, אלא את $V_{\frac {n+1}{4}}(4,1)\!\!\!\!\mod n$. -- רועי.ס - שיחה 16:26, 28 באוגוסט 2014 (IDT)

הבנתי איפה האלגוריתם שלי נופל - בסדרה הזאת ($V(4,1)$), מכיוון שהיא סימטרית מטבעה, אפסים יכולים לבוא רק במקומות שהם כפולות אי-זוגיות של מקום האפס הראשון. עכשיו, מכיוון שבודקים את המקום ה-${\frac {n+1}{4}}$ אם n הוא מספר-מרסן זה מקום שהוא חזקה של 2, כך שאם יש בו 0 זה האפס הראשון, אבל במקרה של 1,037,623, 259,406 הוא לא חזקה של 2, ואכן ה-0 שמופיע שם אינו ה-0 הראשון, אלא ה-9,265. ה-0 הראשון מופיע כבר במקום ה-14. -- רועי.ס - שיחה 23:29, 28 באוגוסט 2014 (IDT)

זה לא מוכרח להיות עניין לניחושים. נוסחת הרקורסיה מראה ש-$\ V_{n}=\alpha ^{n}+\alpha ^{-n}$ כאשר $\ \alpha =2+{\sqrt {3}}$. אם $\ p\equiv \pm 1{\pmod {12}}$ אז 3 הוא שארית ריבועית ולכן alpha בשדה מסדר p והחזקה ה-p-1 שלו היא 1; לכן $\ {\bar {\alpha }}^{(p-1)/2}=\alpha ^{(p-1)/2}=\pm 1$ ואפשר להמשיך ולנתח מהו $\alpha ^{(p+1)/4}$ בהנחה שהחזקה היא מספר שלם. עוזי ו. - שיחה 05:00, 29 באוגוסט 2014 (IDT)

הבנתי (נראה לי) את מה שאמרת, אבל איך זה קשור לנפילת האלגוריתם שלי? מה שהתכוונתי לומר הוא שבגלל שהסדרה ($V(4,1)$) סימטרית סביב המקום ה-0 ואנטי סימטרית סביב כל מקום שיש בו 0 (זה קורה מודלו כל מספר), אפסים יכולים לבוא רק במקומות שהם כפולות אי-זוגיות של מקום האפס הראשון. במספרי-מרסן, המקום שבודקים הוא חזקה של 2, ולכן זה חייב להיות ה-0 הראשון, מודלו כל גורם ראשוני, אך אם יש 0 שנובע מאחד מהגורמים הראשוניים (בינתיים יש לי הוכחה רק למספר שיש לו גורם ראשוני שמשאיר שארית 7 בחלוקה ל-24) מודלו הגורם, אז לא יכול להופיע 0 במקום שבודקים, גם לא מודלו הגורם. אשמח אם תביא את ההוכחה המלאה, רועי.ס - שיחה 09:01, 29 באוגוסט 2014 (IDT)

יש לי תחושה בקשר לדרך הוכחה - מוכיחים בשיטות המערבות רק ענייני התחלקות שלא יכולים להיות למספר גורמים השקולים ל-13 מודלו 24 או ל-5 מודלו 6 ואז מראים בדרך שהראיתי בהודעה הקודמת שלישלא יכול להיות לו גם גורם השקול ל-7 מודלו 24 וכך מסתיימת ההוכחה מכיוון שאי אפשר להגיע למספר השקול ל-7 ע"י מכפלה של מספרים השקולים ל-19 או ל-1. -- רועי.ס - שיחה 09:36, 29 באוגוסט 2014 (IDT)

נניח ש-p ראשוני. $\ V_{(p+1)/4}\equiv 0{\pmod {p}}$ אם ורק אם $\ \alpha ^{(n+1)/4}+\alpha ^{-(n+1)/4}=0$, אם ורק אם $\ \alpha ^{(n+1)/2}=-1$. אני חושד שזה לא קורה לעולם, וצריך להיות n-1 במקום n+1. עוזי ו. - שיחה 14:53, 29 באוגוסט 2014 (IDT)

קח לדוגמא את p=7, שם $V_{\frac {p+1}{4}}=V_{2}=14\equiv _{7}0$ וגם $\alpha ^{\frac {n+1}{2}}=\alpha ^{4}=(2+x)^{4}=16+32x+72+24x+9=97+56x\equiv _{7}-1$, כך שאני לא מבין מה הבעיה כאן. גם עבור p=79, שאינו מספר מרסן, זה קורה וההוכחה בערך מוכיחה גם את זה אם בהתחלה יש את הנוסחה הסגורה ל-$V_{n}$ ולא את המקרה הפרטי שמוכיחים באינדוקציה. -- רועי.ס - שיחה 09:51, 30 באוגוסט 2014 (IDT)

יש לי רעיון איך לשפר את האלגוריתם - במקום לחשב את $V_{\frac {n+1}{4}}\!\!\!\!\mod n$ ולהשוות ל-0, הוא מחשב את $V_{\frac {n+1}{8}}\!\!\!\!\mod n$ ומשווה אותו ל-$4^{\frac {n+1}{8}}\!\!\!\!\mod n$ ול-$-4^{\frac {n+1}{8}}\!\!\!\!\mod n$ ומשווה את $V_{\frac {n+1}{8}}^{2}\!\!\!\!\mod n$ ל-2. אם אחד משני השוויונות הראשונים והשוויון השלישי מתקיימים הוא אומר שהמספר ראשוני, אחרת הוא אומר שהמספר פריק. על כל מספר ראשוני האלגוריתם אומר שהוא ראשוני, מכיוון ש-$V_{\frac {n+1}{8}}^{2}=V_{\frac {n+1}{4}}+2\equiv _{n}2$ (השוויון השלישי) ו-$4^{\frac {n+1}{8}}=2^{\frac {n+1}{4}}$ שהוא השורש של 2 מודלו n ובגלל השוויון השלישי (שכבר הסברתי איך הוא מתקיים) נובע גם שאחד משני השוויונות הראשונים מתקיימים - בדיוק התנאים של החזרת "המספר ראשוני". עוד תוצאה טובה היא שכל מספר שעבורו האלגוריתם הזה טועה, גם האלגוריתם הקודם טועה. זה מתקיים מכיוון שהמספרים שהאלגוריתם הקודם מחזיר עליהם שהם ראשוניים הם בדיוק אלו המקיימים את השוויון השלישי (בעצם ההוכחה שכל מספר ראשוני מקיים את השוויון השלישי עובדת טוב גם כאן) ומכיוון שהאלגוריתם כאן דורש עוד תכונות הרי שהוא טועה לגבי פחות מספרים.

1. נגדיר ברקורסיה את הסדרה $\ V_{n}$ לפי $\ V_{0}=2,\ V_{1}=4$, ו-$\ V_{n}=4V_{n-1}-V_{n-1}$. אז $\ V_{n}=\alpha ^{n}+\alpha ^{-n}$ כאשר $\ \alpha =2+{\sqrt {3}}$.
2. לכן גם $\ V_{n}\equiv 0{\pmod {p}}$ אם ורק אם $\ \alpha ^{2n}=-1$ בהרחבה של השדה מסדר p.
3. 3 הוא שארית ריבועית מודולו p אם $\ p\equiv \pm 1{\pmod {12}}$, ו-3 אינו שארית ריבועית מודולו p אם $\ p\equiv \pm 5{\pmod {12}}$.
4. טענה. אם 3 שארית ריבועית אז $\ \alpha ^{p-1}\equiv 1{\pmod {p}}$. אם 3 אינו שארית ריבועית אז $\ \alpha ^{p+1}\equiv 1{\pmod {p}}$. הוכחה. במקרה הראשון זה משפט פרמה הקטן. במקרה השני $\ \alpha \in \mathbb {F} _{p^{2}}$, ומשפט לגרנז' בחבורה הכפלית של השדה מוכיח רק $\ \alpha ^{p^{2}-1}=1$; אבל מכיוון ש-$\ \alpha$ הוא שורש של הפולינום $\ \lambda ^{2}-4\lambda +1$, הנורמה שלו בהרחבה היא 1, והנורמה שווה לחזקה ה-p+1.
5. בהנתן $\ \alpha ^{N}=1$ (עבור ערך כלשהו של N), אפשר לחשב אחורנית את החזקות ה-N/2^i; בהנחה ש-p אכן ראשוני, מגיעים מתישהו למינוס אחת, או שכל הערכים הם 1 (כמו במבחני הראשוניות המוכרים). עוזי ו. - שיחה 22:50, 30 באוגוסט 2014 (IDT)

אני לא מבין מה הקשר בין מה שאתה אומר לאלגוריתם שלי. -- רועי.ס - שיחה 14:13, 31 באוגוסט 2014 (IDT)

האם במימוש של לוקאס-להמר משתמשים בהתמרת פורייה המהירה כדי להעלות בריבוע את המספרים? כי אם כן אז:

א. האלגוריתם שלי אטי יותר מלוקאס-להמר (בגלל שבאלגוריתם שלי החילוק-עם-שארית לוקח $\lg(n)^{2}$ פעולות ואילו לחלק במספרי-מרסן עם שארית אפשר בזמן $\lg(n)$).

ב. צריך להבהיר בערך שלא מעלים בריבוע בצורה הרגילה, אלא משתמשים בהתמרת פורייה המהירה, מה שמקצר את זמן ההעלאה בריבוע ל-$\lg(n)\lg \left(\lg(n)\right)$ ואת זמן פעולתו של האלגוריתם ל-$\lg(n)^{2}\lg \left(\lg(n)\right)$. -- רועי.ס - שיחה 21:01, 10 בספטמבר 2014 (IDT)