Miller-Rabin-Demo

Miller-Rabin-Demo
with Statistics : with numtheory : with LinearAlgebra :
Zeugenmengen (Div, Euklid, Fermat, Miller-Rabin)
Dwitness d proc N
#
#` `Teilbarkeitszeugen für N
#
divisors N minus 1, N ;
end:
Ewitness d proc N
#
#` `ggT-Zeugen für N
#
select x/evalb igcd N, x O 1 , seq a, a = 2 ..N K 1
end:
Fwitness d proc N
#
#` `Fermat-Euler-Zeugen für N
#
remove x/evalb mod x N K 1 , N = 1 , seq a, a = 2 ..N K 1
end:
MRW dproc N, a
#
# Test, ob a ein Miller-Rabin-Zeuge für die Zusammengesetztheit
# von N ist: Antwort "true" besagt, dass das der Fall ist.
# Bei der Ausgabe wird noch angezeigt, ob a schon ein ggT-Zeuge
# oder eine Fermat-Zeuge für die Zusammengesetzheit ist.
#
local odd, b, e, ee;
#
if `mod` N, 2 = 0 or 1 ! igcd N, a then
RETURN true, `composite:euklid-yes`
end if;
odd := N K 1;
e := 0;
while `mod` odd, 2 = 0 do
odd := odd / 2;
e := e C 1
end do;
b := `mod` a &^ odd, N ;
if `mod` b, N = 1 then
RETURN false, no
end if;
for ee to e do
if `mod` b C 1, N = 0 then
RETURN false, no
end if;
if `mod` b K 1, N = 0 then
RETURN true, `composite:MR-yes`
end if;
b := `mod` b &^ 2, N
end do;
if `mod` b K 1, N = 0 then
RETURN true, `composite:MR-yes`
else
RETURN true, `composite:fermat-yes`
end if
end:
MRwitness d proc N
#
# Miller-Rabin-Zeugen für N
#
remove x/has MRW N, x , false , seq 2 ..N K 1
end:
dw d N/nops Dwitness N
:
ew d N/nops Ewitness N
:
fw d N/nops Fwitness N
:
mrw d N/nops MRwitness N
:
comparew d N/ dw N , ew N , fw N , mrw N
:
N d 14
14
(1.1.1)
2, 7
(1.1.2)
2, 4, 6, 7, 8, 10, 12
(1.1.3)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.1.4)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.1.5)
15
(1.1.6)
Dwitness N
Ewitness N
Fwitness N
MRwitness N
N d 15
Dwitness N
3, 5
(1.1.7)
3, 5, 6, 9, 10, 12
(1.1.8)
2, 3, 5, 6, 7, 8, 9, 10, 12, 13
(1.1.9)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.1.10)
17
(1.1.11)
Ewitness N
Fwitness N
MRwitness N
N d 17
Dwitness N
(1.1.12)
Ewitness N
(1.1.13)
Fwitness N
(1.1.14)
MRwitness N
(1.1.15)
comparew 14
2, 7, 12, 12
(1.1.16)
2, 6, 10, 12
(1.1.17)
3, 7, 14, 14
(1.1.18)
0, 0, 0, 0
(1.1.19)
1, 4, 20, 20
(1.1.20)
6, 21, 28, 28
(1.1.21)
6, 56, 88, 102
(1.1.22)
1, 12, 156, 156
(1.1.23)
6, 240, 240, 550
(1.1.24)
6, 336, 336, 1074
(1.1.25)
6, 432, 432, 1566
(1.1.26)
comparew 15
comparew 16
comparew 17
comparew 25
comparew 30
comparew 105
comparew 169
comparew 561
comparew 1105
comparew 1729
wit d proc N
dw N , ew N K dw N , fw N K ew N , mrw N K fw N , N K 2 K mrw N
end:
W d Transpose Matrix
seq wit N , N = 500 ..600
;
5 x 101 Matrix
Data Type: anything
Storage: rectangular
(1.1.27)
Order: Fortran_order
ColumnGraph convert W, listlist , format = stacked, scale = relative, color = white, yellow,
red, green, blue , gridlines
weiss : D-Zeugen
gelb : E-Zeugen, die keine D-Zeugen sind
rot : F-Zeugen, die keine E-Zeugen sind
grün : MR-Zeugen, die keine F-Zeugen sind
blau : Zahlen, die keine MR-Zeugen sind
Miller-Rabin-Test (probabilistisch)
MRtest dproc N, k
#
#` `MR-Primzahltest für N
# basierend auf der zufälligen Auswahl von k
# Kandidaten, die als Zeugen für die
# Zusammengesetztheit von überprüft werden.
# "true": es wurde ein Zeuge für die
#
Zusammengesetzheit von N gefunden
# "false": keiner der k Kandidaten ist
#
Zeuge - daher: N ist "probable prime"
#
mit Fehlerwahrscheinlichkeit 2^(-k)
local x, s, j;
#
x d rand 2 ..N K 1 ;
s := seq x , j = 1 ..k ;
for j to k do
if has MRW N, op j, s , true then
RETURN "composite"
end if
end do;
RETURN "probably prime"
end proc:
N d 230 C 7
1073741831
(1.2.1)
true
(1.2.2)
"probably prime"
(1.2.3)
1073741819
(1.2.4)
false
(1.2.5)
isprime N
MRtest N, 1
N d 230 K 5
isprime N
ifactor N
361651
2969
(1.2.6)
MRtest N, 1
"composite"
N d 1543595161734337272040623416173
1543595161734337272040623416173
MRtest N, 1
"composite"
(1.2.7)
(1.2.8)
(1.2.9)
ifactor N
1190807
1296259731202736692042139
(1.2.10)
N d 21471 C 7
653316492409148043908692672108874805151000914728843212576132230922411453\ (1.2.11)
92066467932718025309191959466139134777328814412279603162671383395333\
16165007279198774674899221459235486478880552869935137505956400994237\
25706550394338834031345795534912297780823794473941470523222079672835\
27108152128376271035309099916953508202391970618502473012978219898930\
41028107269611873360869157508386900099490458829050874710115614040853\
2803655479443331038049466318855
isprime N
false
(1.2.12)
MRtest N, 1
"composite"
(1.2.13)
"Konstruktion" von Primzahlen mittels MR-Test
findnextprime d proc n, k
#
# Mittels MR-Test wird die kleinste
# "probable" Primzahl, die gösser als n ist,
# gefunden,
# k Parameter für Anzahl der Kandidaten wie in MRtest
#
local N;
#
if `mod` n, 2 = 0 then
N := n C 1
else
N := n
end if;
while MRtest N, k = "composite" do
N := N C 2
end do;
RETURN N, isprime N
end proc:
N d 21471 C 7
6533164924091480439086926721088748051510009147288432125761322309224114539\ (1.3.1)
206646793271802530919195946613913477732881441227960316267138339533316\
165007279198774674899221459235486478880552869935137505956400994237257\
065503943388340313457955349122977808237944739414705232220796728352710\
815212837627103530909991695350820239197061850247301297821989893041028\
107269611873360869157508386900099490458829050874710115614040853280365\
5479443331038049466318855
findnextprime N, 2
(1.3.2)
653316492409148043908692672108874805151000914728843212576132230922411\
453920664679327180253091919594661391347773288144122796031626713833953\
331616500727919877467489922145923548647888055286993513750595640099423\
725706550394338834031345795534912297780823794473941470523222079672835\
271081521283762710353090999169535082023919706185024730129782198989304\
102810726961187336086915750838690009949045882905087471011561404085328\
03655479443331038049466320411, true
IntervallTest dproc n, N, k
#
# findet "probable primes" im Intervall 2nC1 bis 2NC1
# und vergleicht mit Maples Primzahl-Testprozedur.
# Nur die fehlerhaften "Primzahlen" werden angezeigt.
#
select has, seq findnextprime 2 * j C 1, k , j = n ..N , false
end proc:
IntervallTest 10000, 20000, 1
20591, false , 20845, false , 22177, false , 22213, false , 22603, false , 22849, (1.3.3)
false , 22841, false , 23521, false , 23711, false , 24643, false , 24649, false ,
25207, false , 26281, false , 26281, false , 28421, false , 30301, false ,
31417, false , 31621, false , 31621, false , 31753, false , 32551, false ,
37901, false , 38491, false , 38503, false , 38963, false , 39277, false ,
39601, false
IntervallTest 10000, 20000, 2
31621, false , 38503, false
(1.3.4)
IntervallTest 10000, 20000, 3
(1.3.5)