Problēma: dots samērā liels naturāls skaitlis (piem.: 16785927812143), jānosaka vai tas ir pirmskaitlis vai nav. Kā to darīt?

Teorētiķi. Ja neizdodas noteikt ar determinētu Tjūringa mašīnu, tad mēģina noteikt ar nedeterminētu.

Ja vēlas pierādīt, ka dotais naturālais skaitlis nav pirmskaitlis, tad jāuzmin kādu skaitli, ar kuru izdalot nav atlikuma. Tjūringa mašīna tādu skaitli uzmin.

Varbūtisks algoritms – algoritms, kuram var pateikt ar kādu varbūtību tas novedīs pie noteikta rezultāta.

Varbūtisks algoritms rēķina kongruences

Ja p ir noteikta veida, tad eksistē atrisināšanas algoritms, pārējos gadījumos nevar zināt.

Ko parasti dara, ja kāds saka, ka skaitlis ir pirmskaitlis:

Ja nav pāra skaitlis un pēdējais cipars nav 5, tad izmanto Fermā mazo teorēmu no skaitļu teorijas:

Eilera teorēma,

patvaļīgi ņemtam m fii no(m)<p-1.(m- salikts skaitlis) un tad, parasti,

Tāpēc ir ļoti labs algoritms (jāteic gan bezatbildīgs): izvēlas kādu a, viegli rēķināmu, uzceļ pakāpē m-1 un skatās vai iznāk.

Piem: 103 ir vai nav pirmskaitlis?

Ar 2 un 5 nedalās.

Ko mēs uzzinājām? Neko. Ja nebūtu 1, tad zinātu, ka 103 nav pirmskaitlis, bet tagad nevar zināt.

Ko saka šajā ziņā teorija?

Pretējā gadījumā a ir liecinieks tam, ka m ir pirmskaitlis.

T: Vai nu visi skaitļi a, kas ir savstarpēji pirmskaitļi ar m, vai ne vairāk par pusi no visiem skaitļiem, kas ir savstarpēji pirmskaitļi ar m, var būt liecinieki tam, ka m ir pirmskaitlis.

Visi Kārmaikla skaitļi uzrakstāmi formā:

Šie Kārmaikla skaitļi nav pirmskaitļi, bet tai pašā laikā katrs a, kurš ir savstarpējs pirmskaitlis ar Kārmaikla skaitli, liecina, ka pēdējais ir pirmskaitlis.

Tātad nekur tālu neesam tikuši, kaut gan no otras puses, ir ļoti maza varbūtība, ka izvēlētais skaitlis būs Kārmaikla skaitlis.

T: Ja m ir nepāru pirmskaitlis, tad visiem a,

T: Ja m ir nepāru salikts skaitlis, tad vismaz vienai pusei no visiem a ir spēkā

Ko dara Varbūtiskais algoritms?

No nejaušā a, ja ir kongruents , tad neko daudz neesam uzzinājuši, ja nav kongruents, tad m ir salikts skaitlis.

Ņem nākošo a, tad ja ir kongruents, tad ar varbūtību ¼, m varētu būt pirmskaitlis.

Un tātad, ja kaut pie viena a nav kongruents, tad m ir salikts skaitlis, respektīvi, nav pirmskaitlis.

Piem: Vai 2777 ir pirmskaitlis?

ir Jakobi simbols un kā to meklē ir apskatīts lekcijā Nr6.

Tātad iegūstam, ka

Mūs interesē vai

Tātad 2777 nav salikts skaitlis. Bet ticamība, ka tas ir pirmskaitlis ½

Pie kādas tad varbūtības ticēt, ka tas ir pirmskaitlis ?