Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|EchoLisp}}
Line 1,296:
</lang>
=={{header|Elixir}}==
<lang elixir>
defmodule Prime do
use Application
alias :math, as: Math
alias :rand, as: Rand
def start( _type, _args ) do
primes = 5..1000
|> Enum.filter( fn( x ) -> (rem x, 2) == 1 end )
|> Enum.filter( fn( x ) -> miller_rabin?( x, 10) == True end )
IO.inspect( primes, label: "Primes: ", limit: :infinity )
{ :ok, self() }
end
def modular_exp( x, y, mod ) do
with [ _ | bits ] = Integer.digits( y, 2 ) do
Enum.reduce bits, x, fn( bit, acc ) -> acc * acc |> ( &( if bit == 1, do: &1 * x, else: &1 ) ).() |> rem( mod ) end
end
end
def miller_rabin( d, s ) when rem( d, 2 ) == 0, do: { s, d }
def miller_rabin( d, s ), do: miller_rabin( div( d, 2 ), s + 1 )
def miller_rabin?( n, g ) do
{ s, d } = miller_rabin( n - 1, 0 )
miller_rabin( n, g, s, d )
end
def miller_rabin( n, 0, _, _ ), do: True
def miller_rabin( n, g, s, d ) do
a = 1 + Rand.uniform( n - 3 )
x = modular_exp( a, d, n )
if x == 1 or x == n - 1 do
miller_rabin( n, g - 1, s, d )
else
if miller_rabin( n, x, s - 1) == True, do: miller_rabin( n, g - 1, s, d ), else: False
end
end
def miller_rabin( n, x, r ) when r <= 0, do: False
def miller_rabin( n, x, r ) do
x = modular_exp( x, 2, n )
unless x == 1 do
unless x == n - 1, do: miller_rabin( n, x, r - 1 ), else: True
else
False
end
end
end
</lang>
{{out}}
<pre>
Primes: : [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
991, 997]
</pre>
The following larger examples all produce true:
<lang elixir>
miller_rabin?( 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881, 1000 )
miller_rabin?( 138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401, 1000 )
miller_rabin?( 123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841, 1000 )
miller_rabin?( 119432521682023078841121052226157857003721669633106050345198988740042219728400958282159638484144822421840470442893056822510584029066504295892189315912923804894933736660559950053226576719285711831138657839435060908151231090715952576998400120335346005544083959311246562842277496260598128781581003807229557518839, 1000 )
miller_rabin?( 132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731, 1000 )
miller_rabin?( 153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599, 1000 )
miller_rabin?( 103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041, 1000 )
</lang>
=={{header|Erlang}}==
| |||