Miller–Rabin primality test: Difference between revisions

Content added Content deleted
(Added Kotlin)
m (→‎Using Big Integer library: changed the way the random generator is seeded)
Line 1,644: Line 1,644:
===Using Big Integer library===
===Using Big Integer library===
{{libheader|GMP}}
{{libheader|GMP}}
<lang freebasic>' version 29-11-2016
<lang freebasic>' version 05-04-2017
' compile with: fbc -s console
' compile with: fbc -s console


Line 1,650: Line 1,650:
' But we have to define them for older versions.
' But we have to define them for older versions.
#Ifndef TRUE
#Ifndef TRUE
#Define FALSE 0
#Define FALSE 0
#Define TRUE Not FALSE
#Define TRUE Not FALSE
#EndIf
#EndIf


Line 1,661: Line 1,661:
#EndMacro
#EndMacro


Dim Shared As __gmp_randstate_struct rnd_seed
Dim Shared As __gmp_randstate_struct rnd_


Function miller_rabin(big_n As Mpz_ptr, num_of_tests As ULong) As Byte
Function miller_rabin(big_n As Mpz_ptr, num_of_tests As ULong) As Byte
#Macro cleanup
⚫
mpz_clear(n_1) : mpz_clear(a) : mpz_clear(d)
⚫
mpz_clear(n_2) : mpz_clear(x)
#EndMacro


If mpz_cmp_ui(big_n, 1) <= 0 Then
If mpz_cmp_ui(big_n, 1) < 1 Then
Print "Number not allowed"
Print "Numbers smaller then 1 not allowed"
Sleep 5000
Sleep 5000
End If
End If
Line 1,682: Line 1,677:


Dim As ULong r, s
Dim As ULong r, s
Dim As Byte return_value = TRUE

big_int(n_1) : big_int(n_2) : big_int(a) : big_int(d) : big_int(x)
big_int(n_1) : big_int(n_2) : big_int(a) : big_int(d) : big_int(x)


Line 1,688: Line 1,685:
While mpz_tstbit(d, 0) = 0
While mpz_tstbit(d, 0) = 0
mpz_fdiv_q_2exp(d, d, 1)
mpz_fdiv_q_2exp(d, d, 1)
s = s +1
s += 1
Wend
Wend


While num_of_tests > 0
While num_of_tests > 0
num_of_tests -= 1
num_of_tests -= 1
mpz_urandomm(a, @rnd_seed, n_2)
mpz_urandomm(a, @rnd_, n_2)
mpz_add_ui(a, a, 2)
mpz_add_ui(a, a, 2)
mpz_powm(x, a, d, big_n)
mpz_powm(x, a, d, big_n)
Line 1,701: Line 1,698:
mpz_powm_ui(x, x, 2, big_n)
mpz_powm_ui(x, x, 2, big_n)
If mpz_cmp_ui(x, 1) = 0 Then
If mpz_cmp_ui(x, 1) = 0 Then
cleanup
return_value = FALSE
Return FALSE
Exit While
End If
End If
If mpz_cmp(x, n_1) = 0 Then Continue While
If mpz_cmp(x, n_1) = 0 Then Continue While
Line 1,708: Line 1,705:


If mpz_cmp(x, n_1) <> 0 Then
If mpz_cmp(x, n_1) <> 0 Then
cleanup
Return_value = FALSE
Return FALSE
Exit while
End If
End If
Wend
Wend


⚫
mpz_clear(n_1) : mpz_clear(a) : mpz_clear(d)
cleanup
⚫
mpz_clear(n_2) : mpz_clear(x)
⚫
Return TRUE

⚫
Return return_value

End Function
End Function


' ------=< MAIN >=------
' ------=< MAIN >=------


⚫
Dim As Long x
⚫
Dim As ZString Ptr gmp_str : gmp_str = Allocate(10000000)
Dim As String tmp
⚫
Dim As ZString Ptr gmp_str : gmp_str = Allocate(1000000)
big_int(big_n)
big_int(big_n)


Randomize Timer
Randomize Timer
gmp_randinit_mt(@rnd_seed)
gmp_randinit_mt(@rnd_)
gmp_randseed_ui(@rnd_seed, Rnd * &HFFFFFFFF) ' seed the random number generator
For x = 0 To 200 'create seed for random generator
tmp += Str(Int(Rnd * 10))
Next
Mpz_set_str(big_n, tmp, 10)
gmp_randseed(@rnd_, big_n) ' seed the random number generator


⚫
Dim As Long x
For x = 2 To 100
For x = 2 To 100
mpz_set_ui(big_n, x)
mpz_set_ui(big_n, x)
Line 1,739: Line 1,743:
mpz_set_ui(big_n, 1)
mpz_set_ui(big_n, 1)
mpz_mul_2exp(big_n, big_n, x)
mpz_mul_2exp(big_n, big_n, x)
mpz_sub_ui(big_n,big_n,1)
mpz_sub_ui(big_n, big_n, 1)
If miller_rabin(big_n, 5) = TRUE Then
If miller_rabin(big_n, 5) = TRUE Then
gmp_str = Mpz_get_str(0, 10, big_n)
gmp_str = Mpz_get_str(0, 10, big_n)
Line 1,746: Line 1,750:
Next
Next


⚫
gmp_randclear(@rnd_)
Print
⚫
gmp_randclear(@rnd_seed)
mpz_clear(big_n)
mpz_clear(big_n)
DeAllocate(gmp_str)
DeAllocate(gmp_str)


' empty keyboard buffer
' empty keyboard buffer
While InKey <> "" : Wend
Print : While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Print : Print "hit any key to end program"
Sleep
Sleep
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"