Miller–Rabin primality test: Difference between revisions
Content deleted Content added
Added PicoLisp |
→{{header|PureBasic}}: Added task |
||
Line 611: | Line 611: | ||
: (prime? 4547337172376300111955330758342147474062293202868155909393) |
: (prime? 4547337172376300111955330758342147474062293202868155909393) |
||
-> NIL</pre> |
-> NIL</pre> |
||
=={{header|PureBasic}}== |
|||
<lang PureBasic>Enumeration |
|||
#Composite |
|||
#Probably_prime |
|||
EndEnumeration |
|||
Procedure Miller_Rabin(n, k) |
|||
Protected d=n-1, s, x, r |
|||
If n=2 |
|||
ProcedureReturn #Probably_prime |
|||
ElseIf n%2=0 Or n<2 |
|||
ProcedureReturn #Composite |
|||
EndIf |
|||
While d%2=0 |
|||
d/2 |
|||
s+1 |
|||
Wend |
|||
While k>0 |
|||
k-1 |
|||
x=Int(Pow(2+Random(n-4),d))%n |
|||
If x=1 Or x=n-1: Continue: EndIf |
|||
For r=1 To s-1 |
|||
x=(x*x)%n |
|||
If x=1: ProcedureReturn #Composite: EndIf |
|||
If x=n-1: Break: EndIf |
|||
Next |
|||
If x<>n-1: ProcedureReturn #Composite: EndIf |
|||
Wend |
|||
ProcedureReturn #Probably_prime |
|||
EndProcedure</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |