Miller–Rabin primality test: Difference between revisions
Content added Content deleted
Line 4,439: | Line 4,439: | ||
===Standard Probabilistic=== |
===Standard Probabilistic=== |
||
From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#Ruby]] |
From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#Ruby]] |
||
<lang ruby> |
<lang ruby>def miller_rabin_prime?(n, g) |
||
def miller_rabin_prime?(n, g) |
|||
d = n - 1 |
d = n - 1 |
||
s = 0 |
s = 0 |
||
Line 4,461: | Line 4,460: | ||
end |
end |
||
p primes = (3..1000).step(2).find_all {|i| miller_rabin_prime?(i,10)} |
p primes = (3..1000).step(2).find_all {|i| miller_rabin_prime?(i,10)}</lang> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[3, 5, 7, 11, 13, 17, ..., 971, 977, 983, 991, 997]</pre> |
<pre>[3, 5, 7, 11, 13, 17, ..., 971, 977, 983, 991, 997]</pre> |
||
The following larger examples all produce true: |
The following larger examples all produce true: |
||
⚫ | <lang ruby>puts miller_rabin_prime?(94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881,1000) |
||
<lang ruby> |
|||
⚫ | puts miller_rabin_prime?(94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881,1000) |
||
puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000) |
puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000) |
||
puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000) |
puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000) |
||
Line 4,473: | Line 4,470: | ||
puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000) |
puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000) |
||
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000) |
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000) |
||
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000) |
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)</lang> |
||
</lang> |
|||
===Deterministic for integers < 3,317,044,064,679,887,385,961,981=== |
===Deterministic for integers < 3,317,044,064,679,887,385,961,981=== |