פעולת חילוק היא פעולה מורכבת. לכן במקום לעשות חישוב מדויק, כדי לבדוק במהירות את ה”חלקות” של formula_85 נבצע הערכה באמצעות מספר הביטים של הגורמים ש-formula_85 מתחלק בהם, וכך במהירות גבוהה נקבל תוצאות וודאיות במרבית המקרים, ובאלו שיש לגביהם ספק – פשוט זורקים ועוברים הלאה, לא חסרים לנו מספרים לבדוק.
שלב המטריצה.
בשלב זה אנחנו מחזיקים קבוצה formula_102 של מספרים גדולים formula_95 – ואנו צריכים למצוא קבוצה חלקית ל-formula_102 כך שמכפלת האיברים של הקבוצה החלקית תתן מספר ריבועי. לשם כך נגדיר ווקטור של חזקות שמייצג מספרים חלקים מעל בסיס הראשוניים שלנו formula_105.
עבור m מספר חלק מעל B:
formula_106
אנו צריכים למצוא קבוצת וקטורים המייצגים מספרים מתוך formula_102 כך שמכפלת המספרים תהיה מספר ריבועי. לשם כך אנחנו צריכים למצוא קבוצת וקטורי חזקות שסכומם יתן וקטור שכל איבריו זוגיים.
נבנה מטריצה V של וקטורי חזקות, המייצגים formula_85 חלקים מעל B. ועכשיו אנו צריכים למצוא וקטור בינארי e שהכפלתו במטריצה תתן וקטור שכל איבריו זוגיים.
על ידי החילוץ הגאוסיאני () ניתן לפתור את המטריצה, ולקבל וקטור e מתאים.
שיפורים אפשריים.
כדי לעשות זאת קל יותר לחישוב נמיר את המטריצה V למטריצה בינארית V2. ואז וקטור e≠0 שמקיים e·V2=0 יהווה פתרון גם עבור המטריצה V.
חשוב לציין שווקטורים מודולו 2 אינם ייצוג חד חד ערכי של וקטורי חזקות – אולם החסכון בזמן חישוב ובגודל הזיכרון – אפילו שהוא ליניארי בלבד – משתלם למרות הצורך בהחזקת מיפוי בין הווקטור הבינארי למספר המקורי שהוא מייצג.
דוגמאות לייצוג וקטורי מעל בסיס B.
formula_109
formula_110
סיבוכיות.
סיבוכיות הנפה הריבועית תלויה בגודל הבסיס B. בסיס ראשוניים הכולל את כל הראשוניים עד n יביא לכך שכל (Q(x הוא חלק מעל B, וכך תהיה הסיבוכיות למציאת (Q(x מתאים (O(1 בלבד. אולם, גודלה של המטריצה במקרה כזה (כ- (n/log(n ) אינו מאפשר לנו ליהנות מהיעילות של השלב הראשון. מצד שני, בסיס ראשוניים קטן מאוד (למשל הראשוניים עד 1000) ייצר לנו מטריצה קטנה ונוחה לפתרון, ועל כך נשלם בסיכוי זעיר למצוא (Q(x חלק מעל B.
נסמן ב- (φ(X,B את מספר המספרים החלקים מעל B בטווח [X,1]. הסיכוי שמספר אקראי בתחום [X,1] יהיה חלק מעל B הוא φ(X,B)/X, ולכן כדי למצוא מספר אחד מתאים אנחנו צריכים לעבור על (X/φ(X,B מספרים אקראיים. חשוב להדגיש שהמספרים (Q(x אינם אקראיים במובן הפורמלי, אבל כל הניתוחים ההיוריסטיים של שיטות הפירוק נעשים בהנחה שהם אקראיים במידה מספקת. כיוון שאנחנו צריכים B|=k| מספרים כאלו לבניית המטריצה (כדי להבטיח פתרון לא טריוויאלי), אנחנו צריכים לעבור על (k·X/φ(X,B מספרים. עלות הבדיקה שמועמד (Q(x הוא חלק מעל B היא ליניארית ב- B, ולכן העבודה הכוללת בייצור היא (k²·X/φ(X,B פעולות (של ניסיון חילוק מספר בגודל ½n בראשוני קטן).
פומרנץ הראה שכדי לקבל את המינימום עבור הנוסחה הזו צריך שהאיבר הגדול ב-B, אותו סימנו ב- pk, יהיה קרוב ל-
formula_111
, והעבודה הנדרשת היא:
formula_112
, כלומר כ- pk4.
אבל מהו X?
באלגוריתם הניפוי הריבועי אנחנו מייצרים (Q(x מסדר גודל של n½+ε כאשר ε קטן מאוד (מכיוון שמספר המועמדים שנבדוק הוא חזקה קטנה של n); כלומר, formula_113.
לכן, סדר הגודל של שלב הניפוי הוא:
formula_114
לאחר שהנתונים נאספו במטריצה (בגודל k על k), צריך למצוא פתרון לא טריוויאלי, בעלות של (O(k3 (האלימינציה של גאוס). למעשה החלק הזה של האלגוריתם הוא מהיר בהרבה, מכיוון שהמטריצה דלילה. בכל אופן מדובר בסיבוכיות זניחה ביחס לשלב איסוף המשוואות.
נפת שדה המספרים מול הנפה הריבועית.
שיטה נוספת לפירוק מספר לגורמים היא נפת שדה המספרים (Number Field Sieving),
זוהי שיטה מהירה יותר אסימפטוטית מהנפה הריבועית (Quadratic Sieve),
אבל מסובכת הרבה יותר.
שתי השיטות מחולקות לשני שלבים: שלב הניפוי ושלב מטריצה.
סדר הגודל של שלב הניפוי בנפת שדה המספרים הוא: formula_115
כאשר c משתנה לפי סוג הניפוי המדויק בו משתמשים (ברוב המימושים: formula_116).
אסימפטוטית זהו סדר גודל קטן יותר משל הנפה הריבועית, אבל במספרים "קטנים" (עד 100 ספרות) עדיף להשתמש בנפה הריבועית בגלל המסובכות של נפת שדה המספרים.
קרל פומרנץ
אנטאליה
הבי ג'יס
אגואיזם
על-ממלכה
על-ממלכה או דומֵיין (מאנגלית: Domain) היא הרמה העליונה ביותר במבנה ההירארכי של מיון עולם הטבע (טקסונומיה). שיטות המיון המודרניות נוטות לחלק את היצורים לשלוש על-ממלכות:
שיטת המיון המקורית של המדען השוודי קארולוס ליניאוס התבססה על דמיון בתכונות היצורים ובמראם. כיום, עם התפתחות הביולוגיה, הפכה שיטה זו למיושנת. שיטות מיון חדשות שהוצעו, מבוססות בעיקר על דמיון גנטי. כתוצאה מכך, קבוצות רבות של יצורים שנחשבו כיחידות סיסטמטיות, אינן עוד כאלה.
חיידקים אמיתיים וחיידקים קדומים הם יצורים חסרי גרעין (פרוקריוטיים) ואילו האיקריוטיים הם יצורים בעלי גרעין. האיקריוטיים עצמם ממוינים לקבוצות של חד-תאיים כפרוטוזואה ואצות ולשלוש ממלכות: בעלי חיים (Animalia או Metazoa), פטריות (Fungi) וצומח (Plantae או Viridiplantae).
רגוסה (מחוז)
גוואטמלה סיטי
משרד הדאר
אנטגרן
כנסיית סן ז'רמן דה פרה
כנסיית סן-ז'רמן-דה-פרה (צרפתית: Église de Saint-German-des-Prés) היא כנסייה הנמצאת ברובע השישי של פריז. הכנסייה הייתה חלק מהמנזר הבנדיקטי סן-ז'רמן-דה-פרה (Abbey of Saint-Germain-des-Prés), שנבנה בשדות (prés) שמעבר לפרברי פריז של ימי הביניים, היה אתר קבורה של המלכים המרובינגיים של נויסטריה. המנזר, שכיום הוא העתיק ביותר בפריז, נוסד במאה השישית על ידי בנו של כלוביס הראשון, כילדבר הראשון (Childebert I, שלט בשנים 511–558). תחת הפטרונות המלכותית הפך המנזר לאחד העשירים בצרפת. ב אוחסנו בו כתבי קודש חשובים והוא נותר במרכז החיים האינטלקטואליים בכנסייה הקתולית בצרפת עד התפרקותו בזמן המהפכה הצרפתית. פיצוץ ושריפה הרסו את המנזר ואת אכסדרת העמודים שלו, אך הכנסייה שרדה.
על שם המנזר נקרא הרובע שהתפתח סביבו, רובע סן-ז'רמן דה פרה, שמהווה חלק מהרובע הלטיני, משום שהמנזר נידב חלק מאדמותיו לאורך נהר הסן – "שדות המלומדים" (Pré aux Clercs) – לשם הקמת המבנים בהם השתכנה האוניברסיטה של פריז. על שם המנזר נקראות גם השדרות שסמוך להן ממוקמת כיום הכנסייה, שדרות סן ז'רמן.
היסטוריה.
בשנת 542, לאחר שלחם בספרד והסיר את המצור מעל סרגוסה, חזר כילדבר לפריז כשבאמתחתו שריד קדוש יקר ערך שקיבל מהבישוף של סרגוסה, טוּנִיקָה של הקדוש סן-וינסנט, בן העיר. לאחר שחזר כילדבר לפריז, הורה לבנות כנסייה גבוהה כך שיוכל לראותה דרך השדות כדי לאחסן את השריד הקדוש.
בשנת 558 הושלמה בניית כנסיית סן-וינסנט והיא הוקדשה על ידי ז'רמן, ב-23 בדצמבר. באותו היום נפטר כילדבר. מלכי השושלת המרובינגית נטמנו בכנסייה במאות השישית והשביעית, אך קבריהם נפתחו ונהרסו בזמן המהפכה הצרפתית.
לצד הכנסייה נבנה מנזר. לאב המנזר היו סמכויות השיפוט הרוחניות כמו-גם החילוניות באזור הפרבר של סן-ז'רמן (סמכויות בהן החזיק עד לשנת 1670). הכנסייה נבזזה לעיתים תכופות ואף נשרפה במאה התשיעית על ידי הנורמאנים. היא נבנתה מחדש בשנת 1014, והוקדשה מחדש ב - 1163, על ידי האפיפיור אלכסנדר השלישי סן-ז'רמן מפריז, בישוף העיר שהוכרז כקדוש. החומה הגדולה שנבנתה סביב פריז בעת מלוכתו של פיליפ השני לא כללה את שטח המנזר, ולתושביו הותר לדאוג לענייניהם בעצמם.
במאה ה-17 היה מחוז סן-ז'רמן מהאזורים הנחשקים ביותר שבגדה השמאלית. המלכה מרגריט דה ולואה דחקה באב המנזר לנדב גם לה חלק מאדמות המנזר. היא בנתה על השטח ארמון, ושיוותה לאזור סגנון אופנתי, שנותר על כנו עד שמחוז סנט-אונורה שמצפון לשאנז אליזה האפיל עליו בזוהרו במאה ה-18.
מבנה.
למרות השינויים הרבים שעברה הכנסייה, מגדל הפעמון שנישא מעל הכניסה המערבית לא השתנה כמעט מאז שנת 1000, למעט הצריח שנוסף במאה ה-19.
מקום מקהלת הכנסייה שבאפסיס המזרחי הוא דוגמה מוקדמת לבנייה גותית בעזרת תמיכות דואות.
קברו של הפילוסוף רנה דקארט נמצא באחת מהקפלות הצדדיות של הכנסייה.
איונה בראון
איונה בראון (באנגלית: Iona Brown,
7 בינואר 1941 - 5 ביוני 2004) הייתה כנרת ומנצחת בריטית. בעת מותה הייתה מנהלת האקדמיה של סנט מרטין בשדות בלונדון והתזמורת הקאמרית של לוס אנג'לס.
ביוגרפיה.
בראון נולדה למשפחה מוזיקלית; הוריה היו מוזיקאים; אחיה טימותי הוא נגן קרן יער ראשי בתזמורת רשות השידור הבריטית; אח אחר, איאן, הוא פסנתרן ואחותה, סאלי, היא ויולנית בתזמורת הסימפונית של בורנמות'.
משנת 1963 עד 1966, הייתה בראון חברה בתזמורת פילהרמוניה. בשנת 1964 הצטרפה לאקדמיה של סנט מרטין בשדות ושם התקדמה עד להיותה לסולנית בשנת 1974.
בשנת 1981 התמנתה בראון למנהלת אמנותית של התזמורת הקאמרית הנורווגית . ב-1987 קיבלה משרה דומה
בתזמורת הקאמרית של לוס אנג'לס. משנת 1985 עד 1989 הייתה מנהלת אורחת של התזמורת הסימפונית של ברמינגהאם.
בשנים האחרונות, עד מותה, הייתה מנצחת ראשית של התזמורת הסימפונית של דרום יוטלנד, דנמרק.
בראון מתה במחלת הסרטן בגיל 63, בביתה בסולסברי, דרום אנגליה.
מוקצה
מוקצה הוא כינוי לתקנה שתיקנו חכמים, לפיה יש חפצים האסורים בטלטול בשבת וביום טוב. ככלל, כל חפץ שאין לאדם מה לעשות איתו בשבת נחשב למוקצה. יש להבחין בין איסור זה, המתייחס לחפצים מסוימים, לבין "איסור טלטול" הידוע גם כהוצאה מרשות לרשות, הנוגע בטלטול כל חפץ שהוא בין רשויות שבת.
ישנם ארבעה סוגי מוקצה מרכזיים:
טעם התקנה.