---
title: "Rabin-Miller Strong Pseudoprime Test"
type: "forum-thread"
url: "https://www.webforum.nu/amne/matematik/136940-rabin-miller-strong-pseudoprime-test"
topic: "Matematik"
topic_url: "https://www.webforum.nu/amne/matematik"
author: "yohpops"
published: "2005-11-04T09:42:12.000Z"
updated: "2005-11-04T12:44:54.000Z"
replies: 4
views: 613
page: 1
pages: 1
language: "sv-SE"
site: "webForum — webforum.nu"
rights: "Upphovsrätten till varje inlägg tillhör dess författare."
attribution: "Citera som: webForum, https://www.webforum.nu/amne/matematik/136940-rabin-miller-strong-pseudoprime-test"
---

# Rabin-Miller Strong Pseudoprime Test

## #1 — yohpops, 2005-11-04T09:42Z

Kan någon översätta denna metoden till förstålig lekmans matte?
<http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html>

mvh
Y

Permalänk: https://www.webforum.nu/p/136940

## #2 — Muzzafarath, 2005-11-04T10:57Z

Vad räknar du som lekmansmatematik?

Låt n vara ett udda tal.

Finn heltal r, s sådana att n = 2^r \* s + 1 och s inte innehåller någon faktor av 2. (Vilket alltid är möjligt).

Välj ett tal a från intervallet \[1, n - 1\].

Beräkna resten av division av a^s med n. Om denna rest är 1, så "klarar" n testet.

Beräkna resten av division av a^(2^j \* s) med n, för alla j i intervallet \[0, r - 1\]. Om någon av resterna är lika med n - 1, så "klarar" n testet.

Annars "klarar" n inte testet.

Repetera för så många a du känner för (finns säkert uppskattningar på hur stor sannolikheten för att n är ett primtal är beror på hur många olika "a" man testar med).

Permalänk: https://www.webforum.nu/p/1698899

## #3 — yohpops, 2005-11-04T12:12Z

Ok då förstår jag.

Går dessa uppskattningar att räkna ut tro?
Eller blir det isf en uppskattning av en uppskattning?  ;)

Permalänk: https://www.webforum.nu/p/1698932

## #4 — Muzzafarath, 2005-11-04T12:39Z

Stod isf på Mathworld-sidan ser jag nu ;) Sannolikheten att få fel svar (dvs. algoritmen rapporterar ett sammansatt tal som ett primtal) om man utför algoritmen N gånger, är mindre än 1/4^N.

Permalänk: https://www.webforum.nu/p/1698943

## #5 — yohpops, 2005-11-04T12:44Z

Alltså ganska säkert metod?

Permalänk: https://www.webforum.nu/p/1698945

---

Tråden på webben: https://www.webforum.nu/amne/matematik/136940-rabin-miller-strong-pseudoprime-test