אלגוריתם אטלנטיק סיטי
אלגוריתם אטלנטיק סיטי הוא אלגוריתם אקראי הפועל בזמן-פולינומי ועונה בצורה נכונה לפחות 75% מהזמן (או, בכמה גרסאות, ערך אחר גדול מ-50%). המונח "אטלנטיק סיטי" הוצג לראשונה ב-1982 על ידי ג'יי פין בכתב יד שלא פורסם שכותרתו השוואה של בדיקות הסתברותית לבדיקת ראשוניות.[1]
המחלקות הנפוצות האחרות של אלגוריתמים אקראיים הן אלגוריתם מונטה קרלו ואלגוריתם לאס וגאס. אלגוריתם מונטה קרלו הוא תמיד מהיר, אבל צודק רק בהסתברות גבוהה. מצד שני, אלגוריתם לאס וגאס תמיד צודק, אבל מהיר רק בהסתברות גבוהה. אלגוריתם אטלנטיק סיטי הוא אלגוריתם זמן-פולינומי אקראי, שצודק בהסתברות גבוהה ומהיר בהסתברות גבוהה.[2]
הערות שוליים[עריכת קוד מקור | עריכה]
- ^ Richard A. Mollin (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. p. 80.
- ^ William J Turner (במאי 2002). Black Box Linear Algebra with the Linbox Library (PDF). North carolina State University. p. 3. נבדק ב-10 ביולי 2014.
{{cite book}}: (עזרה)