Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Adapted to handle slightly larger figures) |
|||
| Line 1,709: | Line 1,709: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby> |
<lang ruby> |
||
require 'openssl' |
|||
def miller_rabin_prime?(n,g) |
|||
d = n - 1 |
d = n - 1 |
||
s = 0 |
s = 0 |
||
| Line 1,716: | Line 1,718: | ||
s += 1 |
s += 1 |
||
end |
end |
||
g.times do |
|||
a = 2 + rand(n-4) |
a = 2 + rand(n-4) |
||
x = (a**d) % n |
x = OpenSSL::BN::new(a.to_s).mod_exp(d,n) #x = (a**d) % n |
||
next if x == 1 or x == n-1 |
next if x == 1 or x == n-1 |
||
for r in (1 .. s-1) |
for r in (1 .. s-1) |
||
x = (x**2) % n |
x = x.mod_exp(2,n) #x = (x**2) % n |
||
return false if x == 1 |
return false if x == 1 |
||
break if x == n-1 |
break if x == n-1 |
||
| Line 1,734: | Line 1,736: | ||
{{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: |
|||
<lang ruby> |
|||
puts miller_rabin_prime?(94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881,1000) |
|||
puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000) |
|||
puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000) |
|||
puts miller_rabin_prime?(119432521682023078841121052226157857003721669633106050345198988740042219728400958282159638484144822421840470442893056822510584029066504295892189315912923804894933736660559950053226576719285711831138657839435060908151231090715952576998400120335346005544083959311246562842277496260598128781581003807229557518839,1000) |
|||
puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000) |
|||
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000) |
|||
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000) |
|||
</lang> |
|||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||