Miller-Rabin-Test

Transcrição

Miller-Rabin-Test

Miller-Rabin-Demo
with Statistics : with numtheory : with LinearAlgebra :
Miller-Rabin-Test
MRsteps dproc N, aa
#
# 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 Euklid-(ggT)-Zeuge oder ein Fermat-Zeuge
# für die Zusammengesetzheit ist.
# Diese Version print-protokolliert alle
# Schritte des Verfahrens.
#
local odd, a, b, e, ee;
#
if irem N, aa = 0 then RETURN true, `composite:divisibility-yes`
end if;
#
if mod N, 2 = 0 or 1 ! igcd N, aa then RETURN true, `composite:euklid-yes`
#
odd d N K1;
e d 0;
while mod odd, 2 = 0 do
odd d odd / 2;
e d eC1
end do;
b dmod aa &^ odd, N ;
print Zerlegung von NK1:, N K 1 ='odd 2e ','odd'= odd,'e'= e ;
print `a =`, aa ;
if `mod` b, N = 1 then RETURN false, no end if;
for ee to e do
ee K 1
ee K 1
print 'b'2
= 'a'odd$2
, `mod N =`, b ;
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 dmod b &^ 2, N
end do;
e
e
print 'b'2 = 'a'odd$2 , `mod N =`, b ;
end if;
RETURN
true, `composite:MR-yes`
else
RETURN
end if
end proc:
true, `composite:fermat-yes`
N=25
> MRsteps 25, 2
Zerlegung von N-1:, 24 = odd 2e, odd = 3, e = 3
a =, 2
b = a3 , mod N =, 8
b2 = a6 , mod N =, 14
b4 = a12 , mod N =, 21
b8 = a24 , mod N =, 16
true, composite:fermat-yes
> MRsteps 25, 7
(1.1.1.1)
a =, 7
b = a3 , mod N =, 18
> MRsteps 25, 5
b2 = a6 , mod N =, 24
false, no
(1.1.1.2)
true, composite:divisibility-yes
(1.1.1.3)
N=2047
> MRsteps 2047, 2
a =, 2
false, no
(1.1.2.1)
> MRsteps 2047, 3
a =, 3
b = a1023 , mod N =, 1565
b2 = a2046 , mod N =, 1013
(1.1.2.2)
> MRsteps 2047, 10
a =, 10
(1.1.2.3)
b = a1023 , mod N =, 1034
b2 = a2046 , mod N =, 622
> ifactor 2047
23
89
(1.1.2.3)
(1.1.2.4)
N=341
> MRsteps 341, 2
a =, 2
b = a85 , mod N =, 32
b2 = a170 , mod N =, 1
true, composite:MR-yes
(1.1.3.1)
> MRsteps 341, 3
a =, 3
b = a85 , mod N =, 254
b2 = a170 , mod N =, 67
b4 = a340 , mod N =, 56
> MRsteps 341, 16
a =, 16
false, no
> ifactor 341
11
31
(1.1.3.2)
(1.1.3.3)
(1.1.3.4)
N=561
> MRsteps 561, 2
a =, 2
b = a35 , mod N =, 263
b2 = a70 , mod N =, 166
b4 = a140 , mod N =, 67
b8 = a280 , mod N =, 1
true, composite:MR-yes
(1.1.4.1)
> MRsteps 561, 3
> ifactor 561
true, composite:divisibility-yes
3
11
17
(1.1.4.2)
(1.1.4.3)
N=1117
> MRsteps 1117, 2
a =, 2
b = a279 , mod N =, 214
b2 = a558 , mod N =, 1116
false, no
(1.1.5.1)
> MRsteps 1117, 5
a =, 5
b = a279 , mod N =, 214
> isprime 1117
b2 = a558 , mod N =, 1116
false, no
(1.1.5.2)
true
(1.1.5.3)
(1.1.5.3)
Zeugenmengen (Div, Euklid, Fermat, Miller-Rabin)
Dwitness d proc N
#
#` `Teilbarkeitszeugen für N
#
divisors N minus 1, N ;
end proc:
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 proc:
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 proc:
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;
end if;
b dmod b &^ 2, N
end do;
else
RETURN true, `composite:fermat-yes`
end if
end proc:
MRwitness d proc N
#
# Miller-Rabin-Zeugen für N
#
remove x/has MRW N, x , false , seq 2 ..N K 1
end proc:
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=14
> N d 14
> Dwitness N
> Ewitness N
> Fwitness N
> MRwitness N
N := 14
(1.2.1.1)
2, 7
(1.2.1.2)
2, 4, 6, 7, 8, 10, 12
(1.2.1.3)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.2.1.4)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.2.1.5)
N := 15
(1.2.2.1)
3, 5
(1.2.2.2)
N=15
> N d 15
> Dwitness N
> Ewitness N
(1.2.2.3)
> Fwitness N
> MRwitness N
3, 5, 6, 9, 10, 12
(1.2.2.3)
2, 3, 5, 6, 7, 8, 9, 10, 12, 13
(1.2.2.4)
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
(1.2.2.5)
17
(1.2.3.1)
N=17
N d 17
Dwitness N
(1.2.3.2)
Ewitness N
(1.2.3.3)
Fwitness N
(1.2.3.4)
MRwitness N
(1.2.3.5)
N=25
N d 25
25
(1.2.4.1)
5
(1.2.4.2)
5, 10, 15, 20
(1.2.4.3)
Dwitness N
Ewitness N
Fwitness N
2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23
MRwitness N
2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23
(1.2.4.4)
(1.2.4.5)
N=105
N d 105
105
(1.2.5.1)
3, 5, 7, 15, 21, 35
(1.2.5.2)
Dwitness N
Ewitness N
3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 24, 25, 27, 28, 30, 33, 35, 36, 39, 40, 42, 45, (1.2.5.3)
48, 49, 50, 51, 54, 55, 56, 57, 60, 63, 65, 66, 69, 70, 72, 75, 77, 78, 80, 81, 84,
85, 87, 90, 91, 93, 95, 96, 98, 99, 100, 102
Fwitness N
2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28,
(1.2.5.4)
(1.2.5.4)
30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
54, 55, 56, 57, 58, 59, 60, 61, 63, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 77, 78,
79, 80, 81, 82, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 98, 99, 100, 101,
102, 103
MRwitness N
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, (1.2.5.5)
27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68,
69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103
Vergleich der Größe von Zeugenmengen (D,E,F,MR)
> comparew 14
> comparew 15
> comparew 16
> comparew 17
> comparew 25
> comparew 30
> comparew 105
> comparew 169
> comparew 561
> comparew 1105
> comparew 1729
2, 7, 12, 12
(1.2.6.1)
2, 6, 10, 12
(1.2.6.2)
3, 7, 14, 14
(1.2.6.3)
0, 0, 0, 0
(1.2.6.4)
1, 4, 20, 20
(1.2.6.5)
6, 21, 28, 28
(1.2.6.6)
6, 56, 88, 102
(1.2.6.7)
1, 12, 156, 156
(1.2.6.8)
6, 240, 240, 550
(1.2.6.9)
6, 336, 336, 1074
(1.2.6.10)
6, 432, 432, 1566
(1.2.6.11)
(1.2.6.11)
Veranschaulichung
wit :=proc N
dw N ,
ew N K dw N ,
fw N K ew N ,
mrw N K fw N ,
N K2 Kmrw N
# D-Zeugen weiss
# E-Zeugen, die keine D-Zeugen sind gelb
# F-Zeugen, die keine E-Zeugen sind rot
# MR-Zeugen, die keine F-Zeugen sind grün
# Zahlen, die keine MR-Zeugen sind blau
end proc:
Intervall N=550..560
> W1 d Transpose Matrix
W1 :=
seq wit N , N = 550 ..600
5 x 51 Matrix
Data Type: anything
Storage: rectangular
Order: Fortran_order
> ColumnGraph convert W1, listlist ,
format = stacked, scale = relative,
color = white, yellow, red, green, blue ,
gridlines
;
(1.2.7.1.1)
> select n/isprime n , seq n, n = 550 ..600
557, 563, 569, 571, 577, 587, 593, 599
(1.2.7.1.2)
Intervall N=1100..1150
W2 :=
seq wit N , N = 1100 ..1150
5 x 51 Matrix
Data Type: anything
gridlines
;
(1.2.7.2.1)
1103, 1109, 1117, 1123, 1129
(1.2.7.2.2)
Intervall N= 1750..1800
W3 :=
seq wit N , N = 1750 ..1800
5 x 51 Matrix
Data Type: anything
gridlines
;
(1.2.7.2.1.1)
1753, 1759, 1777, 1783, 1787, 1789
(1.2.7.2.1.2)
(1.2.7.2.1.2)
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 d 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:
> N d 230 C 7
> isprime N
> MRtest N, 1
> N d 230 K 5
> isprime N
> ifactor N
> MRtest N, 1
N := 1073741831
(1.3.1)
true
(1.3.2)
"probably prime"
(1.3.3)
N := 1073741819
(1.3.4)
false
(1.3.5)
361651
2969
"composite"
> N d 1543595161734337272040623416173
N := 1543595161734337272040623416173
> MRtest N, 1
> isprime N
"composite"
(1.3.6)
(1.3.7)
(1.3.8)
(1.3.9)
(1.3.10)
false
> ifactor N
1296259731202736692042139
(1.3.11)
> N d 1543595161734337272040623416341
N := 1543595161734337272040623416341
(1.3.12)
> MRtest N, 1
> isprime N
1190807
(1.3.10)
"probably prime"
(1.3.13)
true
(1.3.14)
> N d 21471 C 7
N :=
(1.3.15)
6533164924091480439086926721088748051510009147288432125761322309224\
1145392066467932718025309191959466139134777328814412279603162671383\
3953331616500727919877467489922145923548647888055286993513750595640\
0994237257065503943388340313457955349122977808237944739414705232220\
7967283527108152128376271035309099916953508202391970618502473012978\
2198989304102810726961187336086915750838690009949045882905087471011\
56140408532803655479443331038049466318855
> MRtest N, 1
"composite"
> ifactor N
Warning, computation interrupted
(1.3.16)
"Konstruktion" von MR-Primzahlen
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
N :=
(1.4.1)
65331649240914804390869267210887480515100091472884321257613223092241\
14539206646793271802530919195946613913477732881441227960316267138339\
53331616500727919877467489922145923548647888055286993513750595640099\
42372570655039433883403134579553491229778082379447394147052322207967\
28352710815212837627103530909991695350820239197061850247301297821989\
89304102810726961187336086915750838690009949045882905087471011561404\
08532803655479443331038049466318855
> findnextprime N, 2
(1.4.2)
65331649240914804390869267210887480515100091472884321257613223092241\
14539206646793271802530919195946613913477732881441227960316267138339\
53331616500727919877467489922145923548647888055286993513750595640099\
42372570655039433883403134579553491229778082379447394147052322207967\
28352710815212837627103530909991695350820239197061850247301297821989\
89304102810726961187336086915750838690009949045882905087471011561404\
08532803655479443331038049466320411, 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
20191, false , 20461, false , 20591, false , 20591, false , 20591, false , 20591, (1.4.3)
false , 23047, false , 23521, false , 23651, false , 24301, false , 24589,
false , 38661, false
23521, false , 24727, false , 29341, false
>
(1.4.4)
(1.4.5)

Miller-Rabin-Test

Transcrição

Documentos relacionados

Miller-Rabin-Demo

guter GT Mod - Bockbierbude

BENEFIZ KONZERT

Kleiner Satz von Fermat Hilfssatz: mn ist durch n

Blatt07

Datenblatt Instantaneous water heater 10 bar DH 21400

Umkehrung des Kleinen Satzes von Fermat Kleiner Satz von Fermat

KD91 KS92 KS94 Miniatur-Beschleunigungsaufnehme Miniature

Geschichte der Odd Fellows

Hinterschaft und 2 breite Vorderschäfte für FN Bockdoppelflinte Mod

MOD Steuerungs- und Regel- technik - Bundesverband Modell