Одатда, катта туб сонларни генерация қилишда қуйидаги ёндошувдан фойдаланилади: - 1. Тасодифан берилган узунликдаги (битлар сони бўйича) тоқ сон n танланади.
- 2. Тубликка синаш (тест) ўтказилади.
- 3. Агар n мураккаб сон бўлса, у ҳолда 1-қадамга қайтилади.
Сонларни тубликка текширишнинг эҳтимоллик алгоритмлари - Ферма тести
- Солавей Штрассен тести
- Рабби-Милнер тести
- Бейл-померенц тести
- Лукас тести
- Поклингтон тести
- Прот тести
- Фробениус
Агар п- туб сон бўлса, у ҳолда “Ферманинг кичик теоремаси”га кўра тенглик ўринли бўлади, бунда а ихтиёрий ва п а га каррали эмас. тенгликни бажарилиши берилган п соннинг тублигини аниқловчи зарурий ва етарли шартдир. Яъни агар бирор бир а учун бўлса, у ҳолда п мураккаб сон бўлади, акс ҳолда эса бирор аниқ нарса айтиш қийин, аммо соннинг тублик эҳтимоли ортади. Агар мураккаб сон п учун таққослама бажарилса, у ҳолда п сон а асос бўйича псевдотуб дейилади. Аммо п сон мураккаб бўлганда, шундай а топиладики, таққослама бажарилмайди, бундай а сон п соннинг мураккаблигига гувоҳ дейилади, бунда таққослама бажарилган аввалги а сон эса, п соннинг тублигига “сохта гувоҳ” дейилади. Ферманинг катта сонларни тубликка синаш алгоритми Мураккаб бутун сон п=341(=11∙31) сон 2 асос бўйича псевдотуб дейилади, чунки таққослама бажарилади. Аммо 3 асос бўйича ҳисобланса . Демак, а=2 тубликка “сохта тублик гувоҳи” ва а=3 эса мураккаблик гувоҳи бўлади.
Do'stlaringiz bilan baham: |
